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

题目描述

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

每个楼层 $f$（$0\le f\le N$）恰好住着一位居民，并拥有一个秘密整数

$0\le v_f\le3$，

只有该楼层居民知道它。

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

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

电梯规则

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

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

电梯会在楼层 $f$ 停下并开门，当且仅当：

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

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

居民操作

当电梯停在楼层 $f$ 时：

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

2. 他只能根据：

   • 当前已按下按钮集合；
   • 自己的秘密值 $v_f$；

   来决定操作；

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

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

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

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

所有 $v_f$ 在程序开始前固定，不会变化。

实现要求

共有 $T$ 个测试。

提交一个文件，实现以下两个函数。

居民函数

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

参数：

• subtask：子任务编号，$0\le\text{subtask}\le4$；
• N：最后一个普通楼层编号；
• f：当前楼层；
• v：当前楼层的秘密值 $v_f$；
• p：当前已经按下的按钮，按升序给出。

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

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

每个返回的按钮 $x$ 必须满足：

• $f<x\le N$；
• $x$ 尚未出现在 p 中；
• x 在返回数组中恰好出现一次。

屋顶解码函数

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

参数：

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

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

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

其中第 $i$ 个元素：

• 若 Karlsson 能确定 $v_i$，必须返回正确的 $v_i$；
• 若无法确定，则返回 -1。

重要限制：不能共享状态

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

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

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

因此：

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

所有这些调用必须在总时间限制内完成。

数据范围

• $N=60$；
• $T\le10000$；
• 对所有 $0\le i\le N$，$0\le v_i\le3$。

样例

样例只有 1 个测试，$v_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}

这个方案正确恢复了 $v_0$ 和 $v_2$，其他无法恢复的位置均返回 -1。

子任务

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

计分方式

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

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

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

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

令 $K$ 为某个子任务所有测试用例中恢复数量的最小值。每个子任务只有一个测试文件，但其中最多包含 10000 个测试用例。

得分如下：

子任务	$K$ 的范围	得分
0	-	0
1	$K<60$	$0.25K$
	$K\ge60$	15
2	$K<30$	$0.5K$
	$30\le K<40$	$2K-45$
	$K\ge40$	35
3	$K<30$	$0.5K$
	$K\ge30$	15
4	$K<20$	$0.7K$
	$20\le K<25$	$4K-66$
	$K\ge25$	35

Sample grader

Sample grader 会在同一个进程中模拟全部函数调用。

输入：

• 第一行三个整数 $T,N,S$，分别为测试数、最后一个普通楼层编号、子任务编号；
• 接下来 $T$ 行，每行 $N+1$ 个整数 $v_0,v_1,\dots,v_N$。

输出：

• 第 $i$ 行：第 $i$ 个测试中正确恢复的值数量；
• 第 $T+1$ 行：最终得分。

若需要更详细反馈，可把 grader 第一行的 DETAILED 从 false 改成 true。

若希望 grader 自动生成测试，可把第二行的 AUTO_GENERATE 从 false 改成 true。