分数: 100 点
问题陈述
K社长为JOI决赛阶段的选手们准备了一场游戏。 K社长暗自有一个 N \times N 表 A,每个单元格包含一个非负整数。 让 A_{i,j} 表示写入单元格中的整数 (i + 1)- 从顶部开始的第行 (0 \leq i \leq N - 1)和 (j + 1)- 左起第 1 列 (0 \leq j \leq N - 1)。 桌子 A 满足以下条件。
- 对于每个 i 这样 0 \leq i \leq N - 1,我们有 A_{i,i} = 0.
- 对于每个 i, j 这样 0 \leq i < j \leq N - 1,我们有 A_{i,j} = A_{j,i}.
考虑加权无向图 N 顶点,其中顶点之间的边 i 和顶点 j (0 \leq i < j \leq N - 1) 有重量 A_{i,j}。 让 X 是该图的最小生成树的权重。 换句话说, X 是通过以下过程获得的值。 游戏的目标是让所有参赛者合作并确定 X.
- 设置 x = 0.
- 考虑一个无向图 G 与 N 顶点。 的顶点 G 已编号 0, 1, \dots, N - 1。 最初, G 没有边缘。
- 重复以下操作 N - 1 次。
让 X 的值为 x 在这些之后 N - 1 操作。
- 调用 的顶点 当前可从顶点到达的 G 当前可从顶点到达 0 通过使用一些边缘 顶点附近, 并将其他顶点称为 远顶点。 选择一对 (i, j) 由近顶点组成 i 和一个远顶点 j 使得该值 A_{i,j} \times N^2 + i \times N + j 被最小化。 可以证明至少有一个近顶点和至少一个远顶点,且 (i, j) 是唯一确定的。
- 添加连接顶点的边 i 和顶点 j to G.
- 更新 x \gets x + A_{i,j}.
定义 R = \lfloor 5120 / N \rfloor (其中 \lfloor x \rfloor 表示不超过的最大整数 x)。 有 R \times N JOI决赛阶段的参赛者,分为 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) 执行以下交互。
- K社长赠送参赛者 (r, i) 以下信息。
- 参赛者编号 (r, i),
- 中的信息 (i + 1)- 表格的第 1 行 A,即 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) 来自上一轮的参赛者。
- If r > 0,这些整数在下面描述的交互3中确定。
- If r = 0,那么为了方便我们定义 B_{r,i,0} = B_{r,i,1} = \dots = B_{r,i,N-1} = 0.
- K社长赠送参赛者 (r, i) 以下信息。
如果回答值为 X 不正确,或者如果没有人回答以下值 X 本轮结束时 R - 1,游戏失败。 如果正确的值 X 在回合结束时得到答复 R - 1,游戏成功。 使用的回合数越少,得分越高 (如果轮回给出答案 r,轮数计为 r + 1).
为参赛者实施策略,以便游戏在尽可能少的回合内取得成功。
实施细节
您提交的内容必须包括 multi.h 使用 #include 预处理指令,并且必须实现以下函数。
-
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,j} 写入单元格中 (i + 1)- 从顶部开始的第 1 行 (j + 1)- 表左侧第 1 列 A. - 论点
B是长度为非负整数的序列 N,其中B[j](0 \leq j \leq N - 1) 表示整数 B_{r,i,j} 参赛者发送 (r-1, j) 致参赛者 (r, i)。 如果 r = 0,那么 \texttt{B[j]} = 0. - 该函数必须返回长度为非负整数的序列 1 or N,代表参赛者采取的行动 (r, i) 给出参数中的信息
A,B。 如果返回的序列的长度不是 1 or N,提交判断为 错误答案 [1].- 回答这个值 X is x,该函数必须返回一个长度的序列 1,即 (x)。 如果回答值不正确,则提交判定为 错误答案 [2].
- 如果没有给出答案,该函数必须返回一个序列 B' 长度 N.
- 对于每个 j = 0, 1, \dots, N-1, B'[j] 代表整数 B_{r+1,j,i} 参赛者发送 (r, i) 致参赛者 (r+1, j)。 它必须是介于 0 和 2^{64}-1,包括在内。 请注意,即使当 r = R - 1 和参赛者 (r+1, j) 不存在, 的长度 B' 必须仍然是 N.
- 本轮结束时 R - 1,至少一名参赛者必须给出答案。 如果参赛者没有给出答案,则该提交作品被判定为 错误答案 [3].
- 论点
strategy 或运行时随机性。
如果该函数对相同的参数返回不同的值,则提交被判断为 错误答案 [4].
strategy。
然而, 注意,调用不一定按回合顺序进行 0, 1, \dots, R - 1.
重要说明
- 您可以自由实现其他函数或声明全局变量供内部使用。
- 您提交的程序不得以任何方式与标准输入、标准输出或任何其他文件进行通信。 然而,允许将调试信息等输出到标准错误输出。
约束
- 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) 是整数。
子任务
- (5 点) N \leq 64, A_{i,j} \leq 1 (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
- (10 点) A_{i,j} \leq 1 (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
- (15 点) N \leq 64.
- (40 点) A_{i,j} < 2^{20} (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
- (15 点) A_{i,j} < 2^{40} (0 \leq i \leq N - 1, 0 \leq j \leq N - 1).
- (15 点)没有额外的限制。
评分
如果某个子任务的测试用例中有一个被判断为 错误答案 [1]–[4], 超出时间限制、超出内存限制或运行时错误,则该子任务的分数为 0。 否则,让 S 是该子任务中所有游戏使用的最大回合数。 然后该子任务的分数确定如下。
对于子任务 3
- 无论值 S,该子任务的分数是 100\% 子任务的点数。 如果 S > 6,比赛网站可能会显示“输出部分正确”,但这并不影响分数。
对于子任务 3 以外的子任务
- If S \leq 6,该子任务的分数是 100\% 子任务的点数。
- If 7 \leq S \leq 9,该子任务的分数是 (100 - 20 \cdot (S - 6))\% 子任务的点数。
- If 10 \leq S \leq 19,该子任务的分数是 (40 - S)\% 子任务的点数。
- If 20 \leq S,该子任务的分数是 20\% 子任务的点数。
编译和测试运行
用于测试程序的示例评分器包含在可从竞赛网站下载的存档中。 该存档还包含您必须提交的示例文件。
示例分级器由单个文件组成。
该文件是 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 \leq t \leq T),它输出的结果 t-th 游戏采用以下格式(引号实际上并未打印)。
- 如果游戏成功,则输出该游戏中使用的回合数,如下所示
Accepted: 22. - 如果任何错误答案条件适用,则输出错误答案的类型,如下所示
Wrong Answer [4].
如果正在执行的程序满足多个错误答案条件,则仅显示其中一个。
通讯示例
下面是示例评分器读取的输入示例以及相应的函数调用序列。
示例输入 1
1 3 1 2 3

回合 0,发生以下交互。
- 参赛者 (0, 0) 没有回答的值 X,并发送 B_{1,0,0} = 0 致参赛者 (1, 0), B_{1,1,0} = 1 致参赛者 (1, 1),和 B_{1,2,0} = 2 致参赛者 (1, 2).
- 参赛者 (0, 1) 没有回答的值 X,并发送 B_{1,0,1} = 3 致参赛者 (1, 0), B_{1,1,1} = 4 致参赛者 (1, 1),和 B_{1,2,1} = 5 致参赛者 (1, 2).
- 参赛者 (0, 2) 没有回答的值 X,并发送 B_{1,0,2} = 6 致参赛者 (1, 0), B_{1,1,2} = 7 致参赛者 (1, 1),和 B_{1,2,2} = 8 致参赛者 (1, 2).
由于没有参赛者回答 X,比赛进入下一轮。
回合 1,发生以下交互。
- 参赛者 (1, 0) 收到 B_{1,0,0} = 0 来自参赛者 (0, 0), B_{1,0,1} = 3 来自参赛者 (0, 1),和 B_{1,0,2} = 6 来自参赛者 (0, 2),并回答 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.