这是一道交互题。
有 n+1 个人,由 0 至 n 编号。第 i(0≤i≤n−1) 个人有一个 [0,2m−1] 之间的整数 ai。
编号为 n 的人希望知道 a0+a1+⋯+an−1 的值。为此,他们可以进行如下通讯:
- 首先,选定通讯的秒数 N。
- 接下来的 N 秒中的每一秒,所有 i(0≤i≤n−1) 同时向 (i+1) 发送一个比特的信息。
- 该消息会在下一秒开始前收到。特别地,最后一秒发出的信息不会被收到。
- 除此之外,不允许任何其他形式的通讯。
你需要用尽可能少的通讯秒数完成这个任务。
实现细节
请确保你的程序开头有 #include "mpc.h"
。
你不需要也不应该实现主函数。你需要实现以下两个函数:
int precalc(int n, int m);
n
表示人数,m
表示整数的值域。- 你需要返回通讯的秒数 N。
bool transmit(player &player, int round, int position);
round
表示目前通讯的秒数,其取值为 [1,N] 中的整数;position
表示当前传递信息的人的编号,其取值为 [0,n] 中的整数;player
为一个结构体类型,描述了当前传递信息的人。该结构体实现在mpc.h
中。其包含以下两个成员变量:- 布尔类型变量
last_message
,表示上一秒上一个人传递的信息。若position
为 0 或round
为 1,则last_message
的值一定为 0; - 长度为 4096 的整型数组
memory
,描述当前传递信息的人的“记忆”。- 在
transmit
函数中,这个数组可以被任意修改。 player.memory
只可能在transmit
函数中被修改。若transmit
函数中不对player.memory
进行修改,则同一个人多次传递信息时,player.memory
都存储相同的值。player.memory
的初始值按照以下规则设定:position
不为 n 时,memory
的 0 到 m−1 位取值为 {0,1},从低位到高位描述 aposition 的二进制表示(即第 i 位对应位权 2i 的位),而其余位置为 0;- 否则,该数组的所有位置均为 0。
- 在
- 布尔类型变量
- 你需要返回这个人在这一秒传递给下一个人的信息。
- 当
position
为 n 时或round
为 N 时,该返回值不会产生任何影响。
- 当
在所有 transmit
调用结束后,你需要保证编号为 n 的人的 player.memory
中前 2200 位取值均属于 {0,1},且对应的二进制数是所有 ai 的和。
在满足题目条件和数据范围的情况下,交互库至多消耗 0.15 秒的时间以及 128MiB 的空间。
在程序中使用其他形式的通讯,包括但不限于使用全局变量,会被视为攻击交互库。
测试程序方式
试题目录下提供了一个交互库的参考实现 grader.cpp
。最终测试时所用的交互库实现与该实现有不同,因此选手的解法不应依赖交互库的具体实现。
你需要在本题目录下使用以下编译命令得到可执行程序:
g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm
可执行文件将从标准输入读入以下格式的数据:
- 第一行两个整数 n,m,
- 接下来 n 行每行 m 个
01
整数,从低到高表示每个人的整数的二进制表示,每行的两个整数之间用一个空格分隔。
读入完成后,交互库会先调用一次 init(n,m)
函数得到 N,然后进行 max 轮调用,第 k(1 \le k \le \max(0,N)) 轮调用会调用所有 \text{round}=k 的 transmit
函数,并在调用完之后更新相应的 player.last_message
的值。
- 若 N \le 0,则不会进行任何调用,所有
player.memory
为其初始值。
若你的程序正确运行,可执行文件会输出以下格式的数据:
- 第一行一个长度为 2200 的字符串,表示所有 a_i 的和,按二进制从低位到高位输出。
- 第二行一个字符串,依次输出所有交互完毕后编号为 n 的人的
player.memory
中前 2200 个位置表示的数,相邻两个数之间没有空格。 - 第三行,如果上述两个字符串不同,那么会告知你答案错误;不然,会输出你在这组数据上的得分。
本题目录中同时下发了样例 1.in
,1.ans
以及一个样例程序 mpc.cpp
。该样例程序可以通过下发的样例。
子任务
对于所有测试数据,1 \le n,m \le 2000。
本题共有 10 个子任务,每个子任务 10 分。
子任务编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
n = | 5 | 1000 | 1000 | 1000 | 3 | 10 | 500 | 1000 | 1500 | 2000 |
m = | 5 | 1 | 10 | 30 | 1000 | 1000 | 1000 | 1000 | 1500 | 2000 |
评分方式
本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得 0 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。
在上述条件以外,在一个测试点中,若 N > n+m+100,或者在所有的 transmit
调用结束后编号为 n 的人的 player.memory
中前 2200 位对应的二进制数不是所有 a_i 的和,你会获得 0 分。否则,根据 (N - n - m) 的值,你在该测试点的分数按照以下表格计算:
(N - n - m) \in | [14,100] | [12, 13] | [9, 11] | [6,8] | [5,5] | [4,4] | (-\infty, 3] |
---|---|---|---|---|---|---|---|
分数 | 1 | 2 | 3 | 4 | 6 | 8 | 10 |
你在一个子任务中的分数为该子任务中所有测试点的分数的最小值。