题目描述

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，并且必须实现以下函数。

std::vector<unsigned long long> strategy(int N, int r, int i, std::vector<unsigned long long> A, std::vector<unsigned long long> 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 放在同一目录下，并执行以下命令。

g++ -std=gnu++20 -O2 -o grader grader.cpp multi.cpp

或者，你可以执行压缩包中包含的 compile.sh 文件。在这种情况下，运行以下命令。

./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 条件，则仅显示其中之一。

说明/提示

样例交互

以下是样例评分程序读取的输入示例以及相应的函数调用序列。

输入

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		无额外约束条件。

评分方式

如果在一个子任务的测试用例中，哪怕只有一个被评定为 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%。