P14204 [JOIST 2023] 最后之战 / The Last Battle
题目背景
在洛谷上提交时，只提交一个文件。
在文件头粘贴如下的内容：
```cpp
void Paint(int a, int b, int c);
```
**不要引入任何头文件，并使用 C++20 提交。**
由于交互库实现方式的原因，将时限改为 6s。
题目描述
JOICup 是由 JOI 电视台举办的人气综艺节目。现在 JOICup 进入了最终轮。在最终轮中将进行 “messenger game（信使游戏）”。只有通过第一轮的一支队伍会进行游戏。该队伍由两名选手组成，Anna 和 Bruno。
在信使游戏中，选手们使用一张 $8 \times 8$ 的网格来传递信息。网格的行编号为 $0$ 到 $7$，列编号为 $0$ 到 $7$。
在信使游戏中，Anna 和 Bruno 被隔离在不同的房间。他们将进行 $Q$ 次挑战。第 $i$ 次挑战（$1 \le i \le Q$）按如下流程进行。
1. 主持人 Bitato 给 Anna 一张卡片和一张 $8 \times 8$ 的网格。卡片上写有三个整数 $X_i, Y_i, N_i$（$0 \le X_i \le 7$，$0 \le Y_i \le 7$，$1 \le N_i \le 43$）以及一个由 `A` 和 `B` 组成、长度为 $N_i$ 的字符串 $S_i$。网格上所有单元格最初均为白色。
2. Anna 给满足 “行不等于 $X_i$ 且列不等于 $Y_i$” 的 $49$ 个单元格分别上色。每个被上色的单元格颜色要么是蓝色，要么是红色。
3. Anna 将这张网格交给主持人 Bitato。
4. Bitato 将满足 “行等于 $X_i$ 或列等于 $Y_i$” 的 $15$ 个单元格分别上色。每个被上色的单元格颜色要么是蓝色，要么是红色。此步骤在 Anna 和 Bruno 都看不到的房间内完成。
5. 主持人 Bitato 将一张卡片和网格交给 Bruno。卡片上只写有整数 $N_i$。
6. Bruno 在纸上写下一个字符串。如果它与 $S_i$ 完全一致，Anna 和 Bruno 就赢得这次游戏。
挑战流程如下图所示。
请编写程序，实现 Anna 和 Bruno 的策略，从而赢得 “messenger game”。有关本题的评分方法，请参见下文 “评分”。
### 实现细节（Anna.cpp）
你需要提交两个文件。第一个文件是 `Anna.cpp`，用于实现 Anna 的策略，需实现下列函数。程序应通过预处理指令 `#include` 包含 `Anna.h`。
* `void Anna(int X, int Y, int N, std::string S)`
该函数被调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 次挑战的步骤 1、2、3。
* 参数 $X$ 为第 $i$ 次挑战步骤 1 中卡片上写的整数 $X_i$。
* 参数 $Y$ 为第 $i$ 次挑战步骤 1 中卡片上写的整数 $Y_i$。
* 参数 $N$ 为第 $i$ 次挑战步骤 1 中卡片上写的整数 $N_i$。
* 参数 $S$ 为第 $i$ 次挑战步骤 1 中卡片上写的字符串 $S_i$。
对每次调用 `Anna`，以下函数总计应被调用 $49$ 次。应对恰好那 $49$ 个 “行不等于 $X_i$ 且列不等于 $Y_i$” 的单元格各调用一次下列函数。
* `void Paint(int a, int b, int c)`
* 参数 $a, b$ 表示 Anna 给第 $a$ 行第 $b$ 列的单元格上色。必须满足 $0 \le a \le 7$，$0 \le b \le 7$，$a \ne X$，$b \ne Y$。若不满足，则判为 **Wrong Answer [1]**。
* 参数 $c$ 表示上色的颜色：当 $c = 0$ 时为蓝色，当 $c = 1$ 时为红色。必须满足 $0 \le c \le 1$。若不满足，则判为 **Wrong Answer [2]**。
* 若对相同的 $(a, b)$ 多次调用 `Paint`，则判为 **Wrong Answer [3]**。
* 当 `Anna` 函数结束时，若调用 `Paint` 的次数不是 $49$，则判为 **Wrong Answer [4]**。
### 实现细节（Bruno.cpp）
第二个文件是 `Bruno.cpp`，用于实现 Bruno 的策略，需实现下列函数。程序应通过预处理指令 `#include` 包含 `Bruno.h`。
* `std::string Bruno(int N, std::vector T)`
* 每当 Anna 完成网格上色后调用一次此函数。总计调用 $Q$ 次。第 $i$ 次调用（$1 \le i \le Q$）对应第 $i$ 次挑战的步骤 5、6。
* 参数 $N$ 为第 $i$ 次挑战步骤 5 中卡片上写的整数 $N_i$。
* 参数 $T$ 为大小为 $8 \times 8$ 的二维数组，对应第 $i$ 次挑战步骤 5 中交给 Bruno 的网格。若行号为 $a$（$0 \le a \le 7$）且列号为 $b$（$0 \le b \le 7$）的单元格颜色为蓝色，则有 $\texttt{T[a][b] = 0}$；若为红色，则有 $\texttt{T[a][b] = 1}$。
* 返回值为 Bruno 写在纸上的字符串。
* 若返回值的长度不少于 $44$，则判为 **Wrong Answer [5]**。
* 返回值的每个字符必须是 ‘A’ 或 ‘B’。若不满足，则判为 **Wrong Answer [6]**。
### 重要注意事项
* 你的程序可以实现其他供内部使用的函数，或使用全局变量。提交的文件将与评测器一同编译，生成单一的可执行文件。为避免与其他文件冲突，所有全局变量和内部函数应声明在匿名命名空间中。评测时将以 Anna 和 Bruno 两个进程的形式运行。Anna 进程与 Bruno 进程不能共享全局变量。
* 你的程序不得使用标准输入与标准输出。你的程序不得通过任何方式与其他文件通信。不过，你可以向标准错误输出调试信息。
### 编译与本地测试
你可以从竞赛网页下载包含样例评测器的压缩包以测试你的程序。压缩包中也包含示例程序源码。
样例评测器文件为 `grader.cpp`。要测试你的程序，请将 `grader.cpp`、`Anna.cpp`、`Bruno.cpp`、`Anna.h`、`Bruno.h` 放在同一目录下，并运行以下命令进行编译。你也可以运行压缩包内的 `compile.sh`。
```
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
```
编译成功后会生成可执行文件 `grader`。需要注意，实际评测器与样例评测器不同。特别地，**Bitaro 不一定随机给单元格上色**。样例评测器将以单进程方式运行，从标准输入读取数据并将结果输出到标准输出。
输入格式
样例评测器从标准输入读取如下数据。
> $Q$
> $X_1$ $Y_1$ $N_1$ $S_1$
> $X_2$ $Y_2$ $N_2$ $S_2$
> $\vdots$
> $X_Q$ $Y_Q$ $N_Q$ $S_Q$
输出格式
样例评测器向标准输出输出如下信息（为便于说明加了引号）。
* 若你的程序被判定为正确，它会输出 $L^*$ 的值，如 “$\texttt{Accepted: 28}$”。关于 $L^*$ 的定义，见下文 “评分”。
* 若你的程序被判定为任一种 Wrong Answer，它会输出对应类型，如 “$\texttt{Wrong Answer [1]}$”。
如果你的程序同时满足多种 Wrong Answer 的判定条件，样例评测器只报告其中一种。
在样例评测器中，每次挑战中 Bitaro 选择颜色是由伪随机数决定的，不同次执行的结果不变。要更改伪随机数的种子，请按如下方式以一个整数参数运行样例评测器。
```
./grader 2023
```
说明/提示
### 约束
* $1 \le Q \le 20000$。
* $0 \le X_i \le 7$（$1 \le i \le Q$）。
* $0 \le Y_i \le 7$（$1 \le i \le Q$）。
* $1 \le N_i \le 43$（$1 \le i \le Q$）。
* $Q, X_i, Y_i, N_i$ 为整数。
* $S_i$（$1 \le i \le Q$）为由 ‘$\texttt{A}$’ 与 ‘$\texttt{B}$’ 组成、长度为 $N_i$ 的字符串。
### 评分
若你的程序在任一测试用例中出现实现细节部分的 Wrong Answer [1]–[6] 或任意运行时错误（TLE、MLE、异常结束等），则无论在其他测试用例中是否赢得挑战，得分均为 $0$。否则，令 $L^*$ 为对本题所有测试用例取下述值的最小值。你的得分按下表计算。
* $L$ 的定义为：使得当 $N_i \le L$ 时，Anna 与 Bruno 能赢得所有挑战的最大值。但若他们在全部测试用例中都赢得了所有挑战，则令 $L = 43$。
| $L^*$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Score | 0 | 5 | 8 | 10 | 11 | 13 | 14 | 16 | 18 | 19 | 21 | 22 | 24 | 26 | 27 |
| $L^*$ | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Score | 29 | 30 | 32 | 34 | 35 | 37 | 38 | 40 | 42 | 43 | 45 | 46 | 48 | 50 | 51 |
| $L^*$ | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Score | 53 | 54 | 56 | 57 | 59 | 60 | 62 | 65 | 68 | 71 | 74 | 77 | 84 | 100 |
### 样例交互
下述是样例评测器的一组输入与对应的函数调用。为简洁起见，Bruno 的函数调用参数 $T$ 省略。
### 样例输入 1
```
2
0 0 1 B
5 7 8 AAAABBBB
```
### 样例函数调用
| 调用 Anna 的函数 | 调用 Bruno 的函数 | Bruno 的返回值 |
|---|---|---|
| $\texttt{Anna(0, 0, 1, "B")}$ | | |
| $\texttt{Paint(1, 1, 0)}$ | | |
| $\texttt{Paint(1, 2, 1)}$ | | |
| $\vdots$ | | |
| $\texttt{Paint(7, 7, 1)}$ | | |
| | $\texttt{Bruno(1, ...)}$ | $\texttt{"B"}$ |
| $\texttt{Anna(5, 7, 8, "AAAABBBB")}$ | | |
| $\texttt{Paint(0, 0, 1)}$ | | |
| $\texttt{Paint(0, 1, 1)}$ | | |
| $\vdots$ | | |
| $\texttt{Paint(7, 6, 0)}$ | | |
| | $\texttt{Bruno(8, ...)}$ | $\texttt{"AAAABBBB"}$ |
在这组样例输入中，有 $Q = 2$ 次挑战。
* 第一次挑战中，$X_1 = 0$，$Y_1 = 0$，$N_1 = 1$，$S_1 = \texttt{"B"}$。Anna 给所有 “行不为 $0$ 且列不为 $0$” 的 $49$ 个单元格上色。
* 第二次挑战中，$X_2 = 5$，$Y_2 = 7$，$N_2 = 8$，$S_2 = \texttt{"AAAABBBB"}$。Anna 给所有 “行不为 $5$ 且列不为 $7$” 的 $49$ 个单元格上色。
例如，若你的程序在第一次挑战中调用了 $\texttt{Paint(0, 2, 1)}$，则因为其指定了行号为 $0$ 的单元格而被判为 **Wrong Answer [1]**。
这里还给出样例评测器的另一组输入。
```
30
3 1 1 A
1 4 1 A
6 6 2 AA
1 1 2 BB
3 1 3 BAB
7 4 3 AAB
6 4 4 BAAB
6 7 4 BABA
3 3 5 BABBA
1 5 5 ABBBA
4 3 6 ABBBBB
2 1 6 ABAAAA
6 0 7 AAABABA
6 6 7 BBABBAA
0 4 8 AABAABAB
2 1 8 AABBBBBA
2 0 9 BABABBAAA
1 5 9 BBAAABABB
6 7 10 BAAABAAABB
1 7 10 BBBBBBBABA
2 6 12 AABAABABABAB
3 4 15 BBAABAAAABABAAB
5 6 18 BAAAABBABABBBABBAB
7 0 22 BABBAABAAABBABBBBBBABA
2 0 26 AAAABBABBAAAAABABABBAABAAA
0 7 30 AAABBBAAABAABBBBAABBAAABBBABBB
2 7 34 BABAABBAABABBABAABBABBABAABBBBABBB
2 5 38 BBBBAABAABAABABABBBBBAAABBABAAABAAABBB
5 2 41 AABABBAAABBABAAAABBABABBAAAAAABBABBABBABA
1 0 43 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAAB
```