P17243 [IOI 2026] 课堂游戏 / Classroom Game

塔什干的一所著名高中为庆祝校庆，举办了一场学生和老师之间的游戏。教室里有 $N$ 位同学，编号为 $0$ 到 $N-1$。每位同学手里都有一张纸，纸上写着一个整数数组。最开始时，每张纸都是空白的，也就是上面写着一个空数组。 同学们与 $M$ 位老师（编号为从 $0$ 到 $M-1$）以及校长一起做游戏。游戏总共有 $M$ 步，步数也从 $0$ 编号到 $M-1$。在第 $j$ 步时，第 $j$ 位老师走进教室，接下来就会发生下面的事情： - 有某些（可能为零）同学举手。保证在每一步中，至少有一位同学**不举手**，而且在整个游戏过程中，每位同学**最多举手一次**。 - 老师查看同学们当前手中的纸，并且可以**修改**在这一步中**没有举手**的同学的纸。对于每位这样的同学，教师可以把他手上纸的内容换成一个全新的（可能为空）整数数组。数组中的每个整数必须在 $0$ 到 $63$ 之间（包括 $0$ 和 $63$），而且数组最多包含 $63$ 个元素。 - 在完成这些修改后，第 $j$ 位老师离开教室，同学们根据一个秘密的置换 $P$ 来交换手中的纸。也就是说，每位同学 $i$（$0\le i

```text N M Q[0] Q[1] ... Q[N-1] P[0] P[1] ... P[N-1] ``` 其中，$Q$ 是一个长度为 $N$ 的数组，如果同学 $i$ 在第 $j$ 步举了手，则 $Q[i]=j$；如果同学 $i$ 在整个游戏过程中从来没有举过手，则 $Q[i]=-1$。

在每次调用 `process_step` 后，评测程序示例都会输出纸张的内容。令 $K$ 为 $B$ 的长度，$L[i]$ 为 $B[i]$ 的长度（对于每个 $0\le i

### 例子 设想一个有 $N=4$ 位同学，$M=2$ 位老师，而且置换 $P=[0,3,1,2]$ 的场景。最开始时，所有的纸都是空白的。 评测程序首先调用： ```cpp process_step(4, 2, 0, [1], [[], [], [], []]) ``` 同学 $1$ 已经举手了，因此他手中的纸不能被修改。老师 $0$ 决定在同学 $0$ 的纸上写 $[10]$，在同学 $3$ 的纸上写上 $[1,63,4]$，并且保持同学 $2$ 的纸为空白。为此，该函数必须返回 $$ B=[[10],[],[],[1,63,4]]. $$ 在老师 $0$ 离开后，同学们根据 $P$ 交换纸张。交换后，纸张内容变为 $$ A=[[10],[],[1,63,4],[]]. $$ 评测程序现在调用： ```cpp process_step(4, 2, 1, [0,3], [[10], [], [1,63,4], []]) ``` 同学 $0$ 和 $3$ 已经举手，因此他们手上的纸不能被修改。老师 $1$ 决定在同学 $1$ 的纸上写 $[0,40]$，在同学 $2$ 的纸上写 $[1,50]$。为此，该函数必须返回 $$ B=[[10],[0,40],[1,50],[]]. $$ 老师 $1$ 离开后，纸张再次根据 $P$ 进行交换。交换后，纸张内容变为 $$ A=[[10],[1,50],[],[0,40]]. $$ 最后，评测程序调用： ```cpp determine_steps(4, 2, [[10], [1,50], [], [0,40]]) ``` 该函数必须返回数组 $D=[1,0,-1,1]$，因为同学 $0$ 和 $3$ 在第 $1$ 步举了手，同学 $1$ 在第 $0$ 步举了手，而同学 $2$ 从来没有举过手。在这个例子中，$C=3$。 ### 约束条件 - $2\le N\le 63$ - $1\le M\le 63$ - 在每局游戏的整个过程中，每位同学**最多举手一次**。也就是说，每位同学 $i$ 最多在某一个步骤 $j$ 中举手。 - 在每一步中，至少有一位同学**没有举手**。 ### 子任务与评分 | 子任务 | 分数 | 额外的约束条件 | |:---:|:---:|:---:| | $1$ | $4$ | $M=1$ | | $2$ | $6$ | $N=2$ | | $3$ | $9$ | 对于每个 $0\le i\le N-1$，都有 $P[i]=i$。 | | $4$ | $25$ | 每一步最多有一位同学举手。 | | $5$ | $56$ | 没有额外的约束条件。 | 对于每个测试用例，如果 `process_step` 的任何一次调用的返回结果不符合要求，或者 `determine_steps` 的任何一次调用的返回结果不对，则你的得分为 $0$（在 CMS 中将报告为 `Output isn't correct`）。 否则，令 $C$ 为 `process_step` 所返回的全部 $B$ 中的全部数组的最大长度。然后，在分值为 $S$ 的某个子任务的一个测试用例上，得分将被算为 $S\cdot X$，这里 $X$ 将根据下表由 $C$ 算出： | 条件 | $X$ | |:---:|:---:| | $C\le 2$ | $1.00$ | | $C=3$ | $0.75$ | | $C=4$ | $0.55$ | | $5\le C\le 13$ | $0.50-0.03\cdot(C-5)$ | | $14\le C\le 63$ | $0.19\cdot\dfrac{64-C}{64-14}+0.04$ |