← 返回题目列表

AtCoder · joi2026final_c

C. 多重通讯 2

中文机器翻译题面 查看原题

分数: 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.

  1. 设置 x = 0.
  2. 考虑一个无向图 G 与 N 顶点。 的顶点 G 已编号 0, 1, \dots, N - 1。 最初, G 没有边缘。
  3. 重复以下操作 N - 1 次。 让 X 的值为 x 在这些之后 N - 1 操作。
    1. 调用 的顶点 当前可从顶点到达的 G 当前可从顶点到达 0 通过使用一些边缘 顶点附近, 并将其他顶点称为 远顶点。 选择一对 (i, j) 由近顶点组成 i 和一个远顶点 j 使得该值 A_{i,j} \times N^2 + i \times N + j 被最小化。 可以证明至少有一个近顶点和至少一个远顶点,且 (i, j) 是唯一确定的。
    2. 添加连接顶点的边 i 和顶点 j to G.
    3. 更新 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) 执行以下交互。
    1. 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.
    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 不正确,或者如果没有人回答以下值 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].
    • 保证在使用某个表玩游戏时给定的参数实际上可以发生 A 和提交的函数 strategy。 然而, 注意,调用不一定按回合顺序进行 0, 1, \dots, R - 1.
    • 评分者将在一次执行中玩一场或多场比赛。 在一次执行中,最多调用该函数 10\,240 次。

重要说明

  • 您可以自由实现其他函数或声明全局变量供内部使用。
  • 您提交的程序不得以任何方式与标准输入、标准输出或任何其他文件进行通信。 然而,允许将调试信息等输出到标准错误输出。

约束

  • 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 点)没有额外的限制。

评分

如果某个子任务的测试用例中有一个被判断为 错误答案 [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.