P10431 [JOIST 2024] 三色灯 / Tricolor Lights

在本题中，你需要将两个文件合并成一个文件提交。**不要引入任何头文件**。

在一场游戏中，擅长博弈的 Anna 和 Bruno 将与发牌人 Dealer D-taro 对战。游戏进行时，Anna 和 Bruno 被隔离在不同的房间内，只能通过 Dealer D-taro 进行交流。 在这场游戏中，他们使用一行共 $N$ 盏灯。这些灯自左向右编号为 $1$ 到 $N$，每盏灯都可以被点亮为三种颜色之一：红、绿或蓝。 在游戏开始时，Anna 将每盏灯点亮为红、绿或蓝中的一种。同时，Dealer D-taro 为每盏灯指定一种**禁用颜色**，用一个长度为 $N$ 的字符串 $S$ 表示。令 $S_i$ 表示 $S$ 的第 $i$ 个字符（$1 \le i \le N$）。若 $S_i$ 为 ‘R’，则第 $i$ 盏灯的禁用颜色为红；若为 ‘G’，则禁用颜色为绿；若为 ‘B’，则禁用颜色为蓝。Anna 不能把第 $i$ 盏灯点亮成其禁用颜色。例如，若 $S_i$ 为 ‘R’，则 Anna 不能把第 $i$ 盏灯点成红色。Dealer D-taro 会把每盏灯的禁用颜色信息告知 Anna，但不会告知 Bruno。 在点亮完每盏灯后，Anna 选择一个整数 $l$，满足 $1 \le l \le \min(N, 130)$，并告知 Dealer D-taro。随后 Dealer D-taro 会把灯的总数 $N$ 以及 Anna 选择的整数 $l$ 告知 Bruno。接下来，他们按如下方式进行 $Q$ 轮： 1. Dealer D-taro 选择一个整数 $a_j$，介于 $1$ 与 $N - l + 1$ 之间，并把第 $a_j, a_j+1, \ldots, a_j+l-1$ 盏灯被点亮的颜色序列展示给 Bruno。 2. Bruno 根据所见的颜色序列，向 Dealer D-taro 回复一个整数。若该整数等于 $a_j$，则 Anna 和 Bruno 赢得本轮。 然而，Dealer D-taro 可以根据 Anna 点亮灯的方式以及所选整数 $l$ 来改变对 $a_1, a_2, \ldots, a_Q$ 的选择。 你的任务是实现一个程序，使得 Anna 和 Bruno 能在所有 $Q$ 轮中获胜。 ### 实现细节 你需要提交 $2$ 个文件。 第一个文件为 `Anna.cpp`，用于实现 Anna 的策略。它应实现以下函数，并通过预处理指令 `#include` 包含 `Anna.h`。 * `std::pair anna(int N, std::string S)` 该函数在开始时被调用一次。 * 参数 $N$ 为灯的数量。 * 参数 $S$ 为长度为 $N$ 的字符串，表示 Dealer D-taro 指定的禁用颜色。 * 返回值为一对：字符串 $t$ 表示 Anna 为每盏灯点亮的颜色，以及整数 $l$ 表示 Anna 选择的整数。令 $t_i$ 表示 $t$ 的第 $i$ 个字符（$1 \le i \le N$）。$t_i$ 表示 Anna 将第 $i$ 盏灯点亮为颜色 $t_i$。若 $t_i$ 为 ‘R’，则该灯被点为红；若为 ‘G’，则为绿；若为 ‘B’，则为蓝。 * 字符串 $t$ 的长度必须为 $N$，否则判定为 **Wrong Answer [1]**。 * 字符串 $t$ 的每个字符必须为 ‘R’、‘G’ 或 ‘B’，否则判定为 **Wrong Answer [2]**。 * 每个 $t_i$ 必须与 $S$ 中对应字符不同，否则判定为 **Wrong Answer [3]**。 * $l$ 必须满足 $1 \le l \le \min(N, 130)$，否则判定为 **Wrong Answer [4]**。 第二个文件为 `Bruno.cpp`，用于实现 Bruno 的策略。它应实现以下函数，并通过预处理指令 `#include` 包含 `Bruno.h`。 * `void init(int N, int l)` 该函数在开始时被调用一次。 * 参数 $N$ 为灯的数量。 * 参数 $l$ 为 Anna 选择的整数。 * `int bruno(std::string u)` 在调用 `init` 之后，该函数会被调用 $Q$ 次，对应游戏中每一轮的步骤 $1$ 和 $2$。 * 参数 $u$ 为长度为 $l$ 的字符串，由 ‘R’、‘G’、‘B’ 组成，表示第 $a_j, a_j+1, \ldots, a_j+l-1$ 盏灯被点亮的颜色序列。 * 令 $u_k$ 表示 $u$ 的第 $k$ 个字符（$1 \le k \le l$）。若 $u_k$ 为 ‘R’，则第 $a_j+k-1$ 盏灯被点为红；若为 ‘G’，则为绿；若为 ‘B’，则为蓝。 * 返回值为 Bruno 回复的整数。 * 返回值必须等于 $a_j$，否则判定为 **Wrong Answer [5]**。 ### 重要注意事项 * 你的程序可以实现其他供内部使用的函数，或使用全局变量。提交的文件将与评测器一同编译，合成为一个可执行文件。所有全局变量与内部函数都应声明在匿名命名空间中，以避免与其他文件冲突。实际评测时，Anna 进程与 Bruno 进程会分别运行，两个进程不能共享全局变量。 * 你的程序不得使用标准输入与标准输出。你的程序不得通过任何方式与其他文件通信。但你可以向标准错误输出调试信息。 ### 编译与试运行 你可以从竞赛网页下载包含样例评测器的归档文件，用于本地测试你的程序。 样例评测器文件为 `grader.cpp`。为进行测试，请将 `grader.cpp`、`Anna.cpp`、`Bruno.cpp`、`Anna.h`、`Bruno.h` 置于同一目录，并运行如下命令进行编译。或者，你也可以运行归档文件中的 `compile.sh`。 ```cpp g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp ``` 编译成功后，会生成名为 `grader` 的可执行文件。 请注意，实际评测器不同于样例评测器。样例评测器以单进程方式运行，从标准输入读取输入数据，并向标准输出与标准错误输出写出结果。 ### 评分相关 实际评测程序会根据 Anna 点灯的方式以及所选整数 $l$ 来决定 $a_1, a_2, \ldots, a_Q$。但 Bruno 的回答并不会影响 $a_1, a_2, \ldots, a_Q$ 的选择。

样例评测器从标准输入读取如下数据。 > $N$\ > $S$\ > $Q$\ > $a_1$ $a_2$ $\cdots$ $a_Q$ **与实际评测不同的是**，样例评测器必须有固定答案。$a_j$（$1 \le j \le Q$）表示第 $j$ 轮中 Dealer D-taro 选择的整数。在你的程序中，对于 Anna 选择的整数 $l$，必须满足 $1 \le a_j \le N - l + 1$。

样例评测器会向标准输出与标准错误输出如下输出（引号仅为说明）： * 若答案正确，输出 “$\texttt{Accepted: l}$”，其中 $l$ 为 Anna 选择的整数。 * 若答案错误，则输出出错类型，例如 “Wrong Answer [1]”。 如果你的程序同时满足多类 Wrong Answer 的条件，样例评测器只会报告其中一种。

#### 约束条件 * $1 \le N \le 500\,000$。 * $1 \le Q \le 10\,000$。 * $S$ 为长度为 $N$ 的字符串，仅由 ‘R’、‘G’、‘B’ 组成。 * $N$ 与 $Q$ 为整数。 #### 子任务 1.（5 分）$N \le 131$。 2.（5 分）$N \le 250$。 3.（5 分）$N \le 380$。 4.（15 分）$N \le 7\,000$。 5.（70 分）无额外限制。在该子任务中，得分规则如下： * 令 $l^*$ 表示该子任务所有测试用例中 Anna 选择的 $l$ 的最大值。 * 若该子任务中任意一个测试用例被判定为 **Wrong Answer [1]** ～ **[5]**（见实现细节），或超时、超内存、发生运行时错误，则本子任务得分为 $0$ 分。 * 若该子任务所有测试用例均正确，则得分如下所示： | the value of $l^*$ | score | | :----------------- | :---- | | $61 < l^* \le 130$ | 10 points | | $41 < l^* \le 61$ | 20 points | | $34 < l^* \le 41$ | 25 + 3 x $(41 - l^*)$ points | | $28 < l^* \le 34$ | 46 + 4 x $(34 - l^*)$ points | | $l^* \le 28$ | 70 points | ### 通信示例 下面给出样例评测器的一个输入，以及相应的函数调用过程。 #### 样例函数调用 | Sample Input 1 | 调用 | 返回值 | | - | :---------------------- | :---------------- | | $\texttt{8}\\\texttt{RGGBRBBG}\\\texttt{2}\\\texttt{3 1}$ | `anna(8, "RGGBRBBG")` | `("BBRGBGRR", 5)` | | ^ | `init(8, 5)` | | | ^ | `bruno("RGBGR")` | `3` | | ^ | `bruno("BBRGB")` | `1` | 在该示例中，Anna 接收到灯的数量 $N = 8$ 与禁用颜色字符串 $S = \text{"RGGBRBBC"}$。Anna 选择用字符串 $t = \text{"BBRGBGRR"}$ 点亮每盏灯，并选择整数 $l = 5$，并将其告知 Dealer D-taro。随后，Dealer D-taro 将 $N = 8$ 与 $l = 5$ 告知 Bruno。 在第一轮中，Dealer D-taro 选择 $a_1 = 3$。Bruno 收到表示第 $3,4,5,6,7$ 盏灯颜色的字符串 $u = \text{"RGBGR"}$，并回复整数 $3$，与 $a_1$ 相同。输入样例 $1$ 满足所有子任务的全部约束。可从竞赛网站下载的文件 `sample-01-in.txt` 与输入样例 $1$ 相对应。