P17274 [eJOI 2026] Elevator
题目描述
*这是一道通信题。*
一栋建筑的楼层编号为 $0$ 到 $N$。第 $0$ 层是地面层，第 $N$ 层上方是屋顶。因此，包括屋顶在内，建筑共有 $N+2$ 个层面。
每个满足 $0\le f\le N$ 的楼层 $f$ 都恰好住着一名居民，并且有一个只有该居民知道的秘密整数 $v_f$，其中 $0\le v_f\le 3$。Karlsson 住在屋顶。他的目标是确定 $v_0,v_1,\ldots,v_N$ 中尽可能多的值，而所有居民都会合作，使他能够恢复的值尽可能多。
居民按照以下方式使用建筑内的电梯进行通信。
电梯从第 $0$ 层出发，并且只向上运行。电梯内有编号为 $1$ 到 $N$ 的按钮。最初没有按钮被按下；一个按钮一旦被按下，就会永久保持按下状态。如果 $f=0$，或者第 $f$ 层的按钮已在此前某次停靠时被按下，电梯就会在第 $f$ 层停靠并开门。电梯访问完按钮被按下的最高楼层后，会直接前往屋顶，不再停靠其他楼层；如果始终没有按钮被按下，则从第 $0$ 层直接前往屋顶。
当电梯停在第 $f$ 层时，会依次发生以下事情：
1. 该层居民看到当前所有已按下按钮的完整集合。
2. 仅根据这些信息和 $v_f$，居民可以从尚未按下且对应楼层严格高于 $f$ 的按钮中任选一个子集并按下。
3. 电梯前往更高楼层中按钮已按下的最低楼层；如果按钮已按下的楼层都已访问，则前往屋顶。
如果电梯没有在某层停靠，该层居民就不能按下任何按钮。
电梯到达屋顶时，Karlsson 只能看到最终被按下的按钮集合。他尝试从这些信息中恢复 $v_0,v_1,\ldots,v_N$ 中尽可能多的值。
$v$ 的所有值在程序开始前已经固定，在整个过程中不会改变。
### 实现细节
共有 $T$ 个测试用例。你需要提交一个文件，实现以下两个函数。
```cpp
std::vector press_buttons(int subtask, int N,
int f, int v, std::vector p)
```
- `subtask`：本次调用所属的子任务编号，满足 $0\le\texttt{subtask}\le 4$；
- $N$：最后一个楼层的编号；
- $f$：当前楼层，满足 $0\le f\le N$；
- $v$：第 $f$ 层上的值 $v_f$；
- $p$：当前已按下的按钮，按递增顺序给出。
电梯在第 $f$ 层开门时会调用该函数，即 $f=0$ 或第 $f$ 层按钮已在此前某次停靠时被按下。若电梯没有在某层停靠，则不会为该层调用此函数。
返回值是需要新按下的按钮列表，顺序不限。每个返回的按钮 $x$ 必须满足：
- $f
输入格式
样例评测器会在一次运行中完成所有测试用例的全部函数调用。
输入格式：
- 第 $1$ 行：测试用例数 $T$、最后一个楼层编号 $N$ 和子任务编号 $S$；
- 第 $1+i$ 行：测试用例 $i$ 的 $N+1$ 个整数 $v_0,v_1,\ldots,v_N$。
输出格式
输出格式：
- 第 $i$ 行：测试用例 $i$ 中正确恢复的值的数量；
- 第 $T+1$ 行：最终得分。
如需更详细的反馈，将评测器第一行的宏 `DETAILED` 从 `false` 改为 `true`。如需让评测器自动生成 $v_f$，将第二行的宏 `AUTO_GENERATE` 从 `false` 改为 `true`。
说明/提示
### 样例
样例包含一个测试用例，其楼层值为：
```text
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
```
一次可能的交互如下：
| 选手程序 | 评测程序 |
|---|---|
| | `press_buttons(0, 60, 0, 1, {})` |
| `return {2}` | |
| | `press_buttons(0, 60, 2, 0, {2})` |
| `return {13, 42}` | |
| | `press_buttons(0, 60, 13, 0, {2, 13, 42})` |
| `return {}` | |
| | `press_buttons(0, 60, 42, 1, {2, 13, 42})` |
| `return {}` | |
| | `answer(0, 60, {2, 13, 42})` |
| `return {1, -1, 0, -1, -1, ..., -1}` | |
这次交互正确恢复了下标 $0$ 和 $2$ 处的值。其他返回值均为 $-1$，因为 Karlsson 未能恢复它们。
### 限制
- $N=60$
- $T\le 10\,000$
- 对每个 $0\le i\le N$，均有 $0\le v_i\le 3$
### 子任务
| 子任务 | 分值 | 附加限制 | 获得满分所需恢复的楼层数 |
|:--:|:--:|---|:--:|
| 0 | 0 | 样例。 | - |
| 1 | 15 | $0\le v_i\le 1$；$v_0=v_N=1$；对每个 $0\le i