P9729 [CEOI 2023] Light（征集交互库）

翻译自 CEOI2023 Day1 T1 [Light](https://www.ceoi2023.de/wp-content/uploads/2023/09/1-light.pdf)。

今年 CEOI 的开幕式上有一场精彩的火炬表演。表演者们站成一排，从 $1$ 开始从左往右编号。每个表演者举着一根火炬，初始只有一个举着点燃的火炬的表演者。 表演分为 $Q$ 幕。在第 $a$ 幕开始之前，要么 $p_a > 0$ 个表演者从右侧加入表演，他们的火炬是熄灭的；要么最右侧 $p_a > 0$ 个表演者决定离开，并熄灭他们的火炬（如果他们的火炬是点燃的）。表演者的加入和离开不受委员会的控制。最左侧的表演者永远留在台上。 一旦第 $a$ 幕准备好了，委员会需要宣布一个非负整数 $t_a \geq 0$。对于每个举着点燃的火炬的表演者，用他的火炬点燃他右侧 $t_a$ 个人的火炬。也就是说，第 $i$ 个人的火炬在传火后是点燃的，当且仅当表演者 $\max(1, i - t_a), \cdots, i$ 中至少一个人的火炬在传火前是点燃的。$t_a$ 不应超过 $5p_a$，且越小越好。 在第 $a$ 幕结束时，委员会需要告知每个举着点燃的火炬的表演者是否熄灭火炬。出于美学原因，最右侧的表演者应保持他的火炬点燃。此外，为了节省汽油，点燃的火炬数量不应超过 $150$。 编写程序帮助委员会在上述限制下主持表演。 ### 交互格式 你需要实现以下三个函数： ```c++ void prepare(); ``` 在程序最开始调用。你可以用这个函数做一些预处理，或者什么也不做。 ```cpp pair join(long long p); ``` 当 $p_a > 0$ 个表演者加入时，这个函数被调用。你需要返回 $t_a$ 和这一幕结束后所有火炬保持点燃的表演者的编号，编号列表升序排列。用 `pair` 将这两个信息组合在一起。 ```cpp pair leave(long long p); ``` 当最右侧 $p_a > 0$ 个表演者离开时，这个函数被调用。你需要返回 $t_a$ 和这一幕结束后所有火炬保持点燃的表演者的编号，编号列表升序排列。用 `pair` 将这两个信息组合在一起。 如果任何返回值不符合限制，你的程序将被立刻终止并被判为不正确。你不应从标准输入流读入任何信息，也不应向标准输出流输出任何信息。但是你可以自由写入标准错误流。 你可以将你的程序链接附件中的 `sample_grader.cpp` 进行本地测试。下方有样例交互库的详细描述。 ### 交互库 样例交互库首先从标准输入流中读入整数 $Q$。它会向标准输出流中写入以上三个函数的执行信息。 首先，样例交互库调用 `prepare()`。接下来它将模拟 $Q$ 幕。第 $a$ 幕，交互库将读入一个整数 $p > 0$ 或 $q < 0$。若读入 $p > 0$，说明 $p$ 个表演者加入表演，调用 `join(p)`。若读入 $q < 0$，说明最右侧 $-q$ 个表演者离开表演，调用 `leave(-q)`。 在终止程序后，交互库会向标注输出流写入以下信息之一： - `Invalid input.` 标准输入流的输入不符合上述格式。 - `The stage is empty.` 少于一个表演者留在台上。 - `Invalid return value.` 返回值 $t_a$ 不满足 $0\leq t_a\leq 5p_a$，保持火炬点燃的表演者列表没有升序排列，或列表包含了小于 $1$ 或大于仍在台上的表演者总数的编号。 - `Too many burning torches.` 某一幕结束后大于 $150$ 个火炬保持点燃。 - `Rightmost torch not on fire.` 最右侧的表演者的火炬没有点燃。 - `Not all announced torches have been lit.` 你的程序要求保持点燃的火炬在此之前没有被点燃。 - `Correct: ratio at most f, at most b burning torches.` 没有发生上述错误，所有加入和退出的调用均满足 $t_a\leq f\cdot p_a$（受到浮点数计算误差的影响），且每一幕结束时至多有 $b$ 个火炬保持点燃。 作为对比，实际评测时使用的交互库只会将你的程序判定为 `Not correct`（无论发生了何种上述错误），`Security violation!`，`Partially correct` 或 `Correct`。此外，**交互库自适应**。也就是说，每一幕加入或离开的表演者数量可能取决于你的程序之前和当前的行为。样例交互库和标准交互库都会在你的程序发生上述错误时立刻终止程序。

无

无

#### 样例解释 考虑 $Q = 4$，样例 #1 是交互库和你的程序可能发生的一种交互。输入实际为函数的调用情况，输出实际为程序的返回值。 - `prepare()`：你可以在这个函数被调用时做一些预处理。 - 表演开始，只有一个表演者 $1$，手持点燃的火炬。 - `join(3)`：三个表演者加入。返回 $t_1 = 3$，表演者 $1$ 将表演者 $2, 3, 4$ 的火炬点燃。返回编号列表 $\{2, 4\}$，表演者 $1, 3$ 将自己的火炬熄灭。 - `leave(2)`：最右侧的两个表演者离开。返回 $t_2 = 0$，没有新的火炬被点燃。返回编号列表 $\{2\}$，表演者 $2$ 的火炬保持点燃。 - `join(2)`：两个表演者加入。返回 $t_3 = 3$，表演者 $2$ 将表演者 $3, 4$ 的火炬点燃。返回编号列表 $\{2, 4\}$，表演者 $3$ 将自己的火炬熄灭。 - `join(3)`：三个表演者加入。返回 $t_4 = 3$，表演者 $2$ 将表演者 $3, 5$ 的火炬点燃，表演者 $4$ 将表演者 $5, 6, 7$ 的火炬点燃。返回编号列表 $\{2, 4, 7\}$，表演者 $3, 5, 6$ 将自己的火炬熄灭。 #### 数据范围与评分标准 设 $N$ 表示任意时刻同时在台上的表演者数量的最大值。 - Subtask 1（5 分）：只有一次 `leave` 函数的调用。 - Subtask 2（5 分）：$N\leq 700$。 - Subtask 3（10 分）：$N\leq 5000$。 - Subtask 4（5 分）：$N\leq 2.5\times 10 ^ 4$。 - Subtask 5（10 分）：$N\leq 10 ^ 5$。 - Subtask 6（5 分）：$N\leq 5\times 10 ^ 5$。 - Subtask 7（60 分）：无特殊限制。 **部分评分**：在 Subtask 7 当中，你的实际得分取决于每一幕的 $\frac {t_a} {p_a}$ 的最大值 $P$。如果你希望得到满分，那么必须满足 $t_a \leq p_a$ 的限制。 - 若 $0\leq P\leq 1$，得 $60$ 分。 - 若 $1 < P\leq 2$，得 $35$ 分。 - 若 $2 < P \leq 3$，得 $20$ 分。 - 若 $3 < P\leq 5$，得 $10$ 分。 对于所有数据，$1\leq N\leq 10 ^ {17}$，$1\leq Q\leq 5\times 10 ^ 4$。 #### 限制 时间：1s。 空间：512MB。