#P16895. [EJOI 2026]Elevator

[EJOI 2026]Elevator

电梯(Elevator)

  • 比赛:EJOI 2026 Day 2
  • 时间限制:10 秒
  • 内存限制:每个进程 64 MiB
  • 题目类型:通信题

题目描述

一栋建筑的楼层编号为 00 到 NN。其中 0 层为地面层,NN 层之上是屋顶。因此把屋顶算在内,共有 N+2N+2 个高度层级。

每个楼层 ff(0≤f≤N0\le f\le N)恰好住着一位居民,并拥有一个秘密整数

0≤vf≤30\le v_f\le3,

只有该楼层居民知道它。

Karlsson 住在屋顶。所有居民需要合作,让 Karlsson 最终尽可能恢复出 v0,v1,…,vNv_0,v_1,\dots,v_N 中更多的值。

他们只能通过电梯按钮来通信。

电梯规则

电梯从 0 层出发,只向上运行。

电梯内部有编号 11 到 NN 的按钮。初始时没有任何按钮被按下。一旦某个按钮被按下,它将永久保持按下状态。

电梯会在楼层 ff 停下并开门,当且仅当:

  • f=0f=0;或
  • 楼层 ff 的按钮此前已经被按下。

当电梯访问完所有已经按下按钮对应的楼层后,它会直接前往屋顶,不再在其他楼层停下。

居民操作

当电梯停在楼层 ff 时:

  1. 该居民可以看到当前所有已按下按钮的完整集合;

  2. 他只能根据:

    • 当前已按下按钮集合;
    • 自己的秘密值 vfv_f;

    来决定操作;

  3. 他可以选择按下任意多个尚未按下、且编号严格大于 ff 的按钮;

  4. 电梯随后前往当前已按下但尚未访问的最小楼层;如果没有这样的楼层,则前往屋顶。

如果电梯没有在某层停下,该层居民就无法按任何按钮。

当电梯到达屋顶时,Karlsson 只能看到最终被按下的按钮集合。他必须据此恢复尽可能多的 vfv_f。

所有 vfv_f 在程序开始前固定,不会变化。

实现要求

共有 TT 个测试。

提交一个 C++17 或更新标准的源文件,包含 #include "elevator.h",不要编写 main,实现以下两个函数。

居民函数

std::vector<int> press_buttons(
    int subtask,
    int N,
    int f,
    int v,
    std::vector<int> p
);

参数:

  • subtask:子任务编号,0≤subtask≤40\le\text{subtask}\le4;
  • N:最后一个普通楼层编号;
  • f:当前楼层;
  • v:当前楼层的秘密值 vfv_f;
  • p:当前已经按下的按钮,按升序给出。

函数只会在电梯实际停靠楼层 ff 时被调用。

返回值为当前居民新按下的按钮集合,顺序不限。

每个返回的按钮 xx 必须满足:

  • f<x≤Nf<x\le N;
  • xx 尚未出现在 p 中;
  • x 在返回数组中恰好出现一次。

屋顶解码函数

std::vector<int> answer(
    int subtask,
    int N,
    std::vector<int> p
);

参数:

  • subtask:子任务编号;
  • N:最后一个普通楼层编号;
  • p:最终所有已按下按钮,按升序给出。

每个测试中,当电梯到达屋顶时,该函数恰好调用一次。

返回数组长度必须为 N+1N+1。

其中第 ii 个元素:

  • 若 Karlsson 能确定 viv_i,必须返回正确的 viv_i;
  • 若无法确定,则返回 -1。

重要限制:不能共享状态

楼内人员不能使用按钮以外的任何方式通信。

为了保证这一点,你的程序会运行成 N+2N+2 个独立进程:

  • 每个楼层一个进程;
  • 屋顶一个进程。

因此:

  • 不同楼层不能依靠全局变量共享信息;
  • 楼层进程中最多会有 TT 次 press_buttons 调用;
  • 屋顶进程中恰好有 TT 次 answer 调用;
  • 每个进程拥有独立的 64 MiB 内存。

同一进程内不同测试的调用顺序可能不同;不能利用调用序号在人员之间通信。所有这些调用必须在总时间限制内完成。

数据范围

  • N=60N=60;
  • T≤10000T\le10000;
  • 对所有 0≤i≤N0\le i\le N,0≤vi≤30\le v_i\le3。

样例

样例只有 1 个测试,v0,…,v60v_0,\dots,v_{60} 为:

1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1
1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1

一种合法交互:

Jury:
press_buttons(0,60,0,1,{})

Participant:
return {2}

Jury:
press_buttons(0,60,2,0,{2})

Participant:
return {13,42}

Jury:
press_buttons(0,60,13,0,{2,13,42})

Participant:
return {}

Jury:
press_buttons(0,60,42,1,{2,13,42})

Participant:
return {}

Jury:
answer(0,60,{2,13,42})

Participant:
return {1,-1,0,-1,-1,...,-1}

这个方案正确恢复了 v0v_0 和 v2v_2,其他无法恢复的位置均返回 -1。

子任务

子任务 分值 额外限制 满分所需至少恢复的楼层数
0 样例 -
1 15 0≤vi≤10\le v_i\le1;v0=vN=1v_0=v_N=1;若 vi=0v_i=0,则对每个 0≤i<N0\le i<N 有 vi+1=1v_{i+1}=1 60
2 35 0≤vi≤10\le v_i\le1 40
3 15 0≤vi≤20\le v_i\le2 30
4 35 0≤vi≤30\le v_i\le3 25

计分方式

如果在某个子任务的任一测试中:

  • 返回了错误的已恢复值;
  • 或进行非法操作,例如返回数组长度错误;

则该子任务直接获得 0 分。

对一个测试,定义恢复数量为返回值不等于 -1 的位置数量。

令 KK 为某个子任务所有测试用例中恢复数量的最小值。本地版本每个子任务含原测试文件和新增边界文件,每个文件最多包含 10000 个测试用例;取各文件得分的最小值,分值和公式不变。样例并入第一组执行,样例自身只检查合法性。

得分如下:

子任务 KK 的范围 得分
0 - 0
1 K<60K<60 0.25K0.25K
K≥60K\ge60 15
2 K<30K<30 0.5K0.5K
30≤K<4030\le K<40 2K−452K-45
K≥40K\ge40 35
3 K<30K<30 0.5K0.5K
K≥30K\ge30 15
4 K<20K<20 0.7K0.7K
20≤K<2520\le K<25 4K−664K-66
K≥25K\ge25 35

本地测试附件

下载 elevator.h、sample_grader.cpp 和 sample.in,与自己的 solution.cpp 放在同一目录。

g++ -std=c++17 -O2 solution.cpp sample_grader.cpp -o sample
./sample < sample.in

样例器输入第一行为 T,N,ST,N,S,之后 TT 行,每行 N+1N+1 个秘密值。它逐次模拟合法按钮操作,核对每个已恢复值,逐测试输出恢复数量,最后输出测试数和最少恢复数量。非法按钮、错误恢复值或未达到对应档满分数量时,样例器报错退出。

样例器在一个进程中运行,只用于调试算法;正式评测运行62个独立进程,各楼层测试顺序会打乱。解法应只依赖参数,不依赖其他楼层的全局状态或共享调用序号。