P12081 基础构造练习题 2（P11635 加强版）

本题较 P11635（CTS 2025 Day 2 T2）添加了 $K = 8, 9, 10$ 的情形，并提高了 $K = 6, 7$ 时 $N$ 的限制。注意：P11635 的所有 `unsigned int` 需要修改为 `unsigned long long`。

**这是一道通信题。** 有若干个节点，它们一开始分别存储有一个数字 $a_i \in \{0, 1\}$，它们想要通过 $K$ 轮通信知道其它每个节点存储的数字。 每一轮通信开始的时候，每个节点 $i$ 对每个节点 $j$，都会选择一个数字 $c_{i,j} \in \{0, 1\}$，表示它将会向节点 $j$ 发送数字 $c_{i,j}$，而在这轮通信结束的时候，节点 $j$ 会收到所有节点向它发送的数字的和，具体而言节点 $j$ 会收到一个数字 $s_j = \sum_{i} c_{i,j}$。 现在给定 $K$，你需要找到一个尽量大的 $N$，满足在通过 $K$ 轮通信之后每个节点都可以知道所有节点存储的数字。 ### 实现细节 **你不需要，也不应该实现 `main` 函数。** 你需要实现以下函数： 1. `int init(int K);` - 该函数传入通信总轮数 $K$ 的值。**保证** $1 \leq K \leq 10$。 - 该函数需要返回你选择的节点数量 $N$，**你需要保证** $1 \leq N \leq 60$。 - 对于每次代码运行，**保证在任意 `send` 函数调用前，该函数会被交互库调用恰好一次**。 2. `unsigned long long send(int K, int N, int round, int number, const std::vector& received);` - 该函数传入通信总轮数 $K$，你实现的 `init` 函数返回的节点数量 $N$，当前通信的轮数 `round`，当前你需要实现的节点的编号 `number`，当前节点之前通信的轮数中收到的数字 `received`，其中 `received[0]` 表示这个节点一开始存储的数字，而 `received[i] (1 \leq i < \text{round})` 表示这个节点第 $i$ 轮通信结束的时候收到的数字。**保证** $1 \leq K \leq 10$，$1 \leq \text{round} \leq K + 1$，$0 \leq \text{number} < N$，**且 `received` 的长度为 `round`**。 - 若 $1 \leq \text{round} \leq K$，你需要返回一个无符号 $64$ 位整数 $x$ 表示在这轮通信中节点 `number` 发送给所有节点的数字，其中 $x$ 的第 $i$ 位为节点 `number` 发送给节点 $i$ 的数字，高位用 $0$ 补齐。 - 若 $\text{round} = K + 1$，你需要返回一个无符号 $64$ 位整数 $x$ 表示节点 `number` 经过 $K$ 轮通信后确定的每个节点存储的数字，其中 $x$ 的第 $i$ 位为编号为 $i$ 的节点存储的数字，高位用 $0$ 补齐。 - 对于每次代码运行，**保证该函数会被交互库调用不超过 $10^5$ 次**。 注意：你需要保证，对于任意两次传入参数相同的函数调用（包括 `init` 和 `send`），返回值也应当相同，否则你的程序将会直接被判定为错误。 题目保证在规定的限制下，交互库在每次代码运行中的运行时间不会超过 $100\, \mathrm{ms}$；交互库使用的内存大小固定，且不超过 $64\, \mathrm{MiB}$。这意味着在每次代码运行中你的代码可以使用至少 $900\, \mathrm{ms}$ 的时间和 $448\,\mathrm{MiB}$ 的空间。

无

无

### 测试程序方式 **下发文件中的 `grader.cpp` 是提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此你的解法不应该依赖交互库实现。** 将你的程序命名为 `message.cpp` 并放置于下发文件目录下后，你可以在下发文件目录下使用如下命令进行测试： ```bash g++ grader.cpp message.cpp -o grader -std=c++17 -O2 ./grader ``` 上述脚本将从**标准输入**读入以下格式的数据： - 输入的第一行一个整数 $0$。 - 输入的第二行两个正整数 $T, K$，其中 $T$ 表示进行通信的次数，$K$ 表示每次通信的轮数。你需要保证 $1 \leq T \leq 101$，$1 \leq K \leq 10$。 - 输入的第 $i + 2 (0 \leq i < T)$ 行一个无符号 $64$ 位整数 $x_i$，表示第 $i$ 次通信时每个节点初始存储的数字，其中 $x_i$ 的第 $j$ 位表示 $j$ 号节点初始存储的数字。你需要保证 $\forall 0 \leq i < T, 0 \leq x_i < 2^{64}$。 上述脚本将输出以下格式的数据到**标准输出**： - 若通信结果正确，则输出 `Accepted! (N = [N], K = [K])`； - 若通信结果错误，则输出 `Wrong answer!`。 ### 下发文件说明 在下发文件中： 1. `grader.cpp` 是提供的交互库参考实现。 2. `template_message.cpp` 是提供的示例代码，你可以在此代码的基础上实现。 ### 子任务 本题共有 $10$ 个子任务，每个子任务分值为 $100$ 分，总分为 $1000$ 分。一个子任务的得分为其中所有测试点的得分最小值。 对于所有测试数据，保证 $1 \leq K \leq 10$，且对于每次代码运行，`send` 会被交互库调用不超过 $10^5$ 次。**对于第 $i$ 个子任务，保证 $K = i$。** ### 评分方式 **注意**： - 你不应当通过非法方式获取交互库的内部信息，如试图直接读取交互库中存储的值，或直接与标准输入、输出流进行交互。此类行为将被视为作弊； - **最终的评测交互库与样例交互库的实现有所不同，因此你的解法不应该依赖交互库实现。** **本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 0 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。你只能在程序中访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。 在上述条件基础上，在每个测试点中，程序得到的分数将按照以下方式计算： - 若对于任意两次传入参数相同的该函数调用，返回值不同，则获得 0 分； - 若 $K$ 轮通信后确定的每个节点存储的数字与每个节点初始存储的数字不同，则获得 0 分； - 否则设 $N$ 为调用函数 `init()` 得到的结果，则该测试点的得分为 $s \times {0.7}^{\max(C(K) - N, 0)}$，其中 $s$ 为该测试点的分值，$C(K)$ 的计算方式如下表所示： | 子任务编号 $= K =$ | $C(K) =$ | | :-: | :-: | | $1$ | $2$ | | $2$ | $4$ | | $3$ | $6$ | | $4$ | $11$ | | $5$ | $14$ | | $6$ | $22$ | | $7$ | $26$ | | $8$ | $36$ | | $9$ | $41$ | | $10$ | $47$ |