QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB Total points: 100 Interactive

# 8221. 多方计算

Statistics

这是一道交互题。

有 $n+1$ 个人,由 $0$ 至 $n$ 编号。第 $i(0 \le i \le n-1)$ 个人有一个 $[0,2^m-1]$ 之间的整数 $a_i$。

编号为 $n$ 的人希望知道 $a_0+a_1+\cdots+a_{n-1}$ 的值。为此,他们可以进行如下通讯:

  1. 首先,选定通讯的秒数 $N$。
  2. 接下来的 $N$ 秒中的每一秒,所有 $i(0 \le i \le 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\}$,从低位到高位描述 $a_{\text{position}}$ 的二进制表示(即第 $i$ 位对应位权 $2^i$ 的位),而其余位置为 $0$;
        • 否则,该数组的所有位置均为 $0$。
  • 你需要返回这个人在这一秒传递给下一个人的信息。
    • position 为 $n$ 时或 round 为 $N$ 时,该返回值不会产生任何影响。

在所有 transmit 调用结束后,你需要保证编号为 $n$ 的人的 player.memory 中前 $2200$ 位取值均属于 $\{0,1\}$,且对应的二进制数是所有 $a_i$ 的和。

在满足题目条件和数据范围的情况下,交互库至多消耗 $0.15$ 秒的时间以及 $128\text{MiB}$ 的空间。

在程序中使用其他形式的通讯,包括但不限于使用全局变量,会被视为攻击交互库。

测试程序方式

试题目录下提供了一个交互库的参考实现 grader.cpp。最终测试时所用的交互库实现与该实现有不同,因此选手的解法不应依赖交互库的具体实现。

你需要在本题目录下使用以下编译命令得到可执行程序:

g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm

可执行文件将从标准输入读入以下格式的数据:

  • 第一行两个整数 $n, m$,
  • 接下来 $n$ 行每行 $m$ 个 01 整数,从低到高表示每个人的整数的二进制表示,每行的两个整数之间用一个空格分隔。

读入完成后,交互库会先调用一次 init(n,m) 函数得到 $N$,然后进行 $\max(0,N)$ 轮调用,第 $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.in1.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

你在一个子任务中的分数为该子任务中所有测试点的分数的最小值。