P15941 [JOI Final 2026] 多方通信 2 / Multi Communication 2

K 会长为 JOI 决赛的选手们准备了一个游戏。K 会长秘密地拥有一张 $N \times N$ 的表格 $A$，表格中的每个单元格都包含一个非负整数。令 $A_{i,j}$ 表示写在从上数第 $(i + 1)$ 行（$0 \leq i \leq N - 1$）且从左数第 $(j + 1)$ 列（$0 \leq j \leq N - 1$）单元格中的整数。表格 $A$ 满足以下条件： - 对于每个满足 $0 \leq i \leq N - 1$ 的 $i$，都有 $A_{i,i} = 0$。 - 对于每个满足 $0 \leq i < j \leq N - 1$ 的 $i,j$，都有 $A_{i,j} = A_{j,i}$。 考虑一个具有 $N$ 个顶点的加权无向图，其中顶点 $i$ 和顶点 $j$（$0 \leq i < j \leq N - 1$）之间的边权重为 $A_{i,j}$。令 $X$ 为该图的最小生成树权重。换句话说，$X$ 是通过以下过程获得的值。游戏的目标是让所有选手合作并确定 $X$ 的值。 1. 设置 $x = 0$。 2. 考虑一个具有 $N$ 个顶点的无向图 $G$。$G$ 的顶点编号为 $0, 1, \dots, N-1$。初始时，$G$ 没有边。 3. 重复以下操作 $N - 1$ 次。令 $X$ 为这 $N - 1$ 次操作后的 $x$ 值。 i. 将当前从顶点 $0$ 通过某些边可达的 $G$ 的顶点称为**近端顶点**，将其他顶点称为**远端顶点**。选择一对由近端顶点 $i$ 和远端顶点 $j$ 组成的二元组 $(i, j)$，使得 $A_{i,j} \times N^{2} + i \times N + j$ 的值最小。可以证明，至少存在一个近端顶点和一个远端顶点，并且 $(i, j)$ 是唯一确定的。 ii. 在 $G$ 中添加连接顶点 $i$ 和顶点 $j$ 的边。 iii. 更新 $x \leftarrow x + A_{i,j}$。 定义 $R = \lfloor 5120 / N \rfloor$（其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。JOI 决赛共有 $R \times N$ 名选手，分为 $R$ 个小组，每组 $N$ 名选手。小组编号为 $0$ 到 $R-1$，小组 $r$（$0 \leq r \leq R - 1$）中的选手编号为 $(r,0), (r,1), \dots, (r, N-1)$。 游戏通过按顺序重复以下回合进行：回合 $0, 1, 2, \dots$，最多进行 $R$ 次。在游戏过程中，选手之间不允许交流，但他们可以提前商定策略。 回合 $r$（$0 \leq r \leq R - 1$）按如下方式进行： - 按照 $i = 0, 1, \dots, N - 1$ 的顺序，K 会长与选手 $(r, i)$ 进行以下交互。 1. K 会长给予选手 $(r, i)$ 以下信息： - 该选手的编号 $(r, i)$， - 表格 $A$ 第 $(i + 1)$ 行的信息，即 $A_{i,0}, A_{i,1}, \dots, A_{i,N-1}$， - 整数 $B_{r,i,0}, B_{r,i,1}, \dots, B_{r,i,N-1}$，其中每一个都是介于 $0$ 和 $2^{64} - 1$ 之间（含）的整数，由上一回合的选手发送给选手 $(r, i)$。 - 如果 $r > 0$，这些整数由下文描述的交互 3 确定。 - 如果 $r = 0$，为了方便起见，我们定义 $B_{r,i,0} = B_{r,i,1} = \dots = B_{r,i,N-1} = 0$。 2. 如果选手 $(r, i)$ 能够确定 $X$ 的值，他们向 K 会长回答该值。如果任何选手给出了答案，游戏立即结束。 3. 对于每个 $j = 0, 1, \dots, N - 1$，选手 $(r, i)$ 确定一个整数 $B_{r+1,j,i}$（必须在 $0$ 到 $2^{64} - 1$ 之间，含），发送给选手 $(r + 1, j)$，并将其告知 K 会长。即使当 $r = R - 1$ 导致选手 $(r + 1, j)$ 不存在时，选手 $(r, i)$ 仍必须确定 $B_{r+1,j,i}$ 并告知 K 会长。 如果回答的 $X$ 值不正确，或者到回合 $R - 1$ 结束时仍没有人回答 $X$ 的值，则游戏失败。如果在回合 $R - 1$ 结束前回答了正确的 $X$ 值，则游戏成功。使用的回合数越少，得分越高（如果在回合 $r$ 给出答案，回合数计为 $r + 1$）。 请为选手们实现一种策略，使游戏以尽可能少的回合数成功。 ### 实现细节 你的提交必须~~使用 `#include` 预处理指令包含 multi.h~~，并且必须实现以下函数。 ```cpp std::vector strategy(int N, int r, int i, std::vector A, std::vector B) ``` - 参数 $N$ 代表表格 $A$ 的行数和列数。 - 参数 $r$ 和 $i$ 代表选手编号 $(r,i)$。 - 参数 $A$ 是一个长度为 $N$ 的非负整数序列，其中 $A[j]$（$0 \leq j \leq N-1$）代表写在表格 $A$ 从上数第 $(i+1)$ 行、从左数第 $(j+1)$ 列单元格中的整数 $A_{i,j}$。 - 参数 $B$ 是一个长度为 $N$ 的非负整数序列，其中 $B[j]$（$0 \leq j \leq N-1$）代表从选手 $(r-1,j)$ 发送给选手 $(r,i)$ 的整数 $B_{r,i,j}$。如果 $r=0$，则 $B[j]=0$。 - 该函数必须返回一个长度为 $1$ 或 $N$ 的非负整数序列，代表选手 $(r,i)$ 根据参数 $A, B$ 中的信息所采取的行动。如果返回的序列长度不是 $1$ 或 $N$，提交将被评定为 **Wrong Answer [1]**。 - 要回答 $X$ 的值为 $x$，该函数必须返回一个长度为 $1$ 的序列，即 $(x)$。如果回答的值不正确，提交将被评定为 **Wrong Answer [2]**。 - 如果不给出回答，该函数必须返回一个长度为 $N$ 的序列 $B'$。 - 对于每个 $j=0,1,\dots,N-1$，$B'[j]$ 代表由选手 $(r,i)$ 发送给选手 $(r+1,j)$ 的整数 $B_{r+1,j,i}$。它必须是介于 $0$ 和 $2^{64}-1$ 之间（含）的整数。请注意，即使当 $r=R-1$ 且选手 $(r+1,j)$ 不存在时，$B'$ 的长度仍必须为 $N$。 - 在回合 $R-1$ 结束前，至少要有一名选手给出回答。如果没有选手给出回答，提交将被评定为 **Wrong Answer [3]**。 - 该函数的返回值必须仅由其参数决定。特别注意，返回值不得依赖于之前对 `strategy` 的调用或运行时的随机性。如果该函数对相同的参数返回不同的值，提交将被评定为 **Wrong Answer [4]**。 - 保证给定的参数在利用某个表格 $A$ 和提交的函数 `strategy` 进行游戏时确实可能发生。但是，请注意，调用不一定按照回合 $0,1,\dots,R-1$ 的顺序进行。 - 评分程序将在单次执行中进行一场或多场游戏。在一次执行中，该函数最多被调用 $10240$ 次。 ### 重要注意事项 - 你可以自由实现其他函数或声明全局变量以供内部使用。 - 你提交的程序不得以任何方式与标准输入、标准输出或任何其他文件进行通信。但是，允许向标准错误输出输出调试信息等。 ### 编译与测试运行 用于测试程序的样例评分程序包含在可从竞赛网站下载的压缩包中。该压缩包还包含你必须提交的样例文件。 样例评分程序由单个文件组成，即 `grader.cpp`。要测试你的程序，请将文件 `grader.cpp`、`multi.cpp` 和 `multi.h` 放在同一目录下，并执行以下命令。 ```bash g++ -std=gnu++20 -O2 -o grader grader.cpp multi.cpp ``` 或者，你可以执行压缩包中包含的 `compile.sh` 文件。在这种情况下，运行以下命令。 ```bash ./compile.sh ``` 如果编译成功，将生成一个名为 `grader` 的可执行文件。 请注意，用于评测的实际评分程序与样例评分程序不同。样例评分程序以单进程运行。该程序从标准输入读取输入，并将结果写入标准输出。

样例评分程序在单次执行中进行一场或多场游戏。 首先，样例评分程序从标准输入读取游戏数量 $T$。然后，对于 $T$ 场游戏中的每一场，它按以下格式读取表格 $A$ 的信息。 > $N$\ > $A_{0,1} \ A_{0,2} \ A_{0,3} \ \cdots \ A_{0,N-1}$\ > $A_{1,2} \ A_{1,3} \ \cdots \ A_{1,N-1}$\ > $\vdots$\ > $A_{N-2,N-1}$

样例评分程序向标准输出输出 $T$ 行。在第 $t$ 行（$1 \le t \le T$），它按以下格式输出第 $t$ 场游戏的结果（引号实际上不会被打印）。 * 如果游戏成功，则输出该游戏使用的回合数，如 `Accepted: 22`。 * 如果触发了任何 Wrong Answer 条件，则输出 Wrong Answer 的类型，如 `Wrong Answer [4]`。 如果执行的程序满足多个 Wrong Answer 条件，则仅显示其中之一。

### 样例交互 以下是样例评分程序读取的输入示例以及相应的函数调用序列。 **输入** ```text 1 3 1 2 3 ``` | 调用 strategy | 返回值 | |:-:|:-:| | $\texttt{strategy(3,\,0,\,0,\,[0,\,1,\,2],\,[0,\,0,\,0])}$ | $\texttt{[0,\,1,\,2]}$ | | $\texttt{strategy(3,\,0,\,1,\,[1,\,0,\,3],\,[0,\,0,\,0])}$ | $\texttt{[3,\,4,\,5]}$ | | $\texttt{strategy(3,\,0,\,2,\,[2,\,3,\,0],\,[0,\,0,\,0])}$ | $\texttt{[6,\,7,\,8]}$ | | $\texttt{strategy(3,\,1,\,0,\,[0,\,1,\,2],\,[0,\,3,\,6])}$ | $\texttt{[3]}$ | 在第 $0$ 回合中，发生了以下交互： - 选手 $(0,0)$ 没有回答 $X$ 的值，并向选手 $(1,0)$ 发送 $B_{1,0,0} = 0$，向选手 $(1,1)$ 发送 $B_{1,1,0} = 1$，向选手 $(1,2)$ 发送 $B_{1,2,0} = 2$。 - 选手 $(0,1)$ 没有回答 $X$ 的值，并向选手 $(1,0)$ 发送 $B_{1,0,1} = 3$，向选手 $(1,1)$ 发送 $B_{1,1,1} = 4$，向选手 $(1,2)$ 发送 $B_{1,2,1} = 5$。 - 选手 $(0,2)$ 没有回答 $X$ 的值，并向选手 $(1,0)$ 发送 $B_{1,0,2} = 6$，向选手 $(1,1)$ 发送 $B_{1,1,2} = 7$，向选手 $(1,2)$ 发送 $B_{1,2,2} = 8$。 由于没有选手回答 $X$ 的值，游戏进入下一回合。 在第 $1$ 回合中，发生了以下交互： - 选手 $(1,0)$ 收到来自选手 $(0,0)$ 的 $B_{1,0,0} = 0$，来自选手 $(0,1)$ 的 $B_{1,0,1} = 3$，以及来自选手 $(0,2)$ 的 $B_{1,0,2} = 6$，并回答 $X = 3$。由于回答了 $X$ 的值，游戏在此结束。 因为回答的 $X$ 值是正确的，游戏成功。该游戏使用的回合数为 $2$。 此样例输入满足子任务 $3, 4, 5$ 和 $6$ 的约束条件。 在可从竞赛网站下载的文件中，`sample-01-in.txt` 对应于样例输入 1。 从竞赛网站下载的压缩包中还包含其他样例输入：`sample-02-in.txt`、`sample-03-in.txt` 和 `sample-04-in.txt`。`sample-02-in.txt` 满足所有子任务的约束条件，`sample-03-in.txt` 满足子任务 $3, 4, 5$ 和 $6$ 的约束条件，`sample-04-in.txt` 满足子任务 $4, 5$ 和 $6$ 的约束条件。 ### 约束条件 - $2 \leq N \leq 256$。 - $0 \leq A_{i,j} < 2^{48}$ ($0 \leq i \leq N-1$, $0 \leq j \leq N-1$)。 - $A_{i,i}=0$ ($0 \leq i \leq N-1$)。 - $A_{i,j}=A_{j,i}$ ($0 \leq i < j \leq N-1$)。 - $N$ 和 $A_{i,j}$ ($0 \leq i \leq N-1, 0 \leq j \leq N-1$) 均为整数。 ### 子任务 | 子任务 | 分值 | 描述 | |:-:|:-:|:-| | 1 | $5$ | $N \leq 64$, $A_{i,j} \leq 1$ ($0 \leq i \leq N-1, 0 \leq j \leq N-1$)。 | | 2 | $10$ | $A_{i,j} \leq 1$ ($0 \leq i \leq N-1, 0 \leq j \leq N-1$)。 | | 3 | $15$ | $N \leq 64$。 | | 4 | $40$ | $A_{i,j} < 2^{20}$ ($0 \leq i \leq N-1, 0 \leq j \leq N-1$)。 | | 5 | $15$ | $A_{i,j} < 2^{40}$ ($0 \leq i \leq N-1, 0 \leq j \leq N-1$)。 | | 6 | $15$ | 无额外约束条件。 | ### 评分方式 如果在一个子任务的测试用例中，哪怕只有一个被评定为 **Wrong Answer [1]-[4]**、Time Limit Exceeded、Memory Limit Exceeded 或 Runtime Error，则该子任务的分数为 $0$。否则，令 $S$ 为该子任务所有游戏中使用的最大回合数。那么该子任务的分数确定如下： #### 对于子任务 3 - 无论 $S$ 的值是多少，该子任务的分数均为该子任务分值的 100%。如果 $S > 6$，竞赛网站可能会显示“Output is partially correct”，但这不影响得分。 #### 对于子任务 3 以外的子任务 - 如果 $S \leq 6$，该子任务的分数为该子任务分值的 100%。 - 如果 $7 \leq S \leq 9$，该子任务的分数为该子任务分值的 $(100-20 \cdot (S-6))\%$。 - 如果 $10 \leq S \leq 19$，该子任务的分数为该子任务分值的 $(40-S)\%$。 - 如果 $20 \leq S$，该子任务的分数为该子任务分值的 20%。