题目描述

这是一道通信题。

一栋建筑的楼层编号为 $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$ 个测试用例。你需要提交一个文件，实现以下两个函数。

std::vector<int> press_buttons(int subtask, int N,
                               int f, int v, std::vector<int> 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<x\le N$；
• $x$ 不在 $p$ 中，并且在返回数组中恰好出现一次。

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

• subtask：本次调用所属的子任务编号，满足 $0\le\texttt{subtask}\le 4$；
• $N$：最后一个楼层的编号；
• $p$：最终已按下的按钮集合，按递增顺序给出。

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

返回数组的长度必须为 $N+1$。如果 Karlsson 能恢复 $v_i$，则其第 $i$ 个元素应等于 $v_i$；否则应为 $-1$。

重要： 建筑内的人不能通过按钮之外的任何方式通信。你的程序会作为 $N+2$ 个相互独立的进程运行：每个楼层一个进程，屋顶一个进程。每个楼层进程最多收到 $T$ 次 press_buttons 调用，屋顶进程恰好收到 $T$ 次 answer 调用。因此，程序不得假设存在任何共享状态，例如全局变量。每个进程分别拥有 64 MiB 内存；总计至多 $(N+1)T$ 次 press_buttons 调用和恰好 $T$ 次 answer 调用都必须在 10 秒内完成。

输入格式

样例评测器会在一次运行中完成所有测试用例的全部函数调用。

输入格式：

• 第 $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。

提示

样例

样例包含一个测试用例，其楼层值为：

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

一次可能的交互如下：

这次交互正确恢复了下标 $0$ 和 $2$ 处的值。其他返回值均为 $-1$，因为 Karlsson 未能恢复它们。

限制

• $N=60$
• $T\le 10\,000$
• 对每个 $0\le i\le N$，均有 $0\le v_i\le 3$

子任务

评分

如果程序在某个子任务的任何测试用例中返回了错误恢复值或执行了非法操作，例如返回长度错误的 vector，则该子任务得 $0$ 分。

对于一个测试用例，恢复数量是返回值不等于 $-1$ 的位置数。令 $K$ 为该子任务所有测试用例中恢复数量的最小值。每个子任务只有一个测试，其中包含至多 $10\,000$ 个测试用例。得分按下表计算：