AT_joisc2017_e 壊れた機器 (Broken Device)

**这是一道通信题。** Anna 和 Bruno 是考古学家，他们正在伊朗调查遗迹。 他们的任务如下：Anna 前往遗迹并发现文物，Bruno 在大本营分析结果。 他们的调查计划持续 $Q(=1000)$ 天。每天，Anna 使用通信设备将结果发送给 Bruno。每天的结果以一个整数 $X$ 表示。 Anna 每天只能使用一次通信设备。它可发送一个长度为 $N(=150)$、由 0 或 1 组成的序列。 然而，该设备已损坏。在长度为 $N$ 的序列中，存在若干损坏位置。对于损坏位置，无论实际设定值为何，设备总是发送值 0。当 Anna 发送序列时，她可以看到损坏位置的位置，但 Bruno 不知道这些位置。损坏位置的位置和数量每天都会变化。 存在调查可能被延误的危险。由于你是伊朗某国际编程竞赛的参赛者，Anna 和 Bruno 请求你编写一个程序，用于发送他们的调查结果。 **任务** 编写两个程序，以实现 Anna 和 Bruno 之间的通信： - 给定序列长度 $N$、待发送的整数 $X$、损坏位置数量 $K$ 以及损坏位置 $P$，第一个程序设置 Anna 发送的序列 $S$。 - 给定 Bruno 接收到的序列 $A$，第二个程序恢复整数 $X$。 在通信设备正常工作的位置，序列 $S$ 与序列 $A$ 的值相同。在损坏位置，无论序列 $S$ 的值为何，序列 $A$ 总是值 0。 **实现细节** 你需要提交两个使用**相同编程语言**编写的文件。 第一个文件为 `Anna.c` 或 `Anna.cpp`。该文件用于设置 Anna 发送的序列，并实现以下函数。程序中应包含 `Annalib.h`。 - `void Anna( int N, long long X, int K, int P[] )` 对于每个测试用例，该函数将被调用 $Q = 1000$ 次。 - 参数 $N$ 表示待发送序列的长度。 - 参数 $X$ 是待发送的整数。 - 参数 $K$ 是损坏位置的数量。 - 参数 $P[]$ 是一个长度为 $K$ 的序列，描述损坏位置的位置。 在函数 `Anna` 中，必须调用以下函数： - `void Set( int pos, int bit )` 该函数用于设置通信设备将要发送的序列 $S$ 中的某一位。 - 参数 `pos` 是待设置位置的索引，其值必须是介于 0 到 $N - 1$（含）之间的整数。请注意，位置从 0 开始计数。若使用超出此范围的参数调用该函数，你的程序将被视为 **Wrong Answer[1]**。不允许使用相同的参数 `pos` 多次调用该函数；若发生此情况，你的程序将被视为 **Wrong Answer[2]**。 - 参数 `bit` 是设置到序列第 `pos` 位的值，其值必须为 0 或 1。若使用其他参数调用该函数，你的程序将被视为 **Wrong Answer[3]**。 函数 `Set` 在函数 `Anna` 中必须被**恰好调用 $N$ 次**。当函数 `Anna` 结束时，若函数 `Set` 的调用次数与 $N$ 不一致，你的程序将被视为 **Wrong Answer[4]**。 若函数 `Anna` 的调用被视为无效，你的程序将被终止。 第二个文件为 `Bruno.c` 或 `Bruno.cpp`。该文件用于恢复表示调查结果的整数，并实现以下函数。程序中应包含 `Brunolib.h`。 - `long long Bruno( int N, int A[] )` 对于每个测试用例，该函数将被调用 $Q = 1000$ 次。 - 参数 $N$ 是 Bruno 接收到的序列的长度。 - 参数 $A$ 是一个长度为 $N$ 的整数序列，即 Bruno 接收到的序列。 - 函数 `Bruno` 必须恢复出 $X$ 的值并返回它。 **评分流程** 评分按以下方式进行。若你的程序被视为 **Wrong Answer**，则立即被终止。 （1）设置 `cnt = 0`。 （2）调用函数 `Anna` 一次。 （3）令 $S$ 为函数 `Anna` 设置的序列。在序列 $S$ 中，将位置 $P$ 上的值设为 0，得到序列 $A$。以参数 $A$ 调用函数 `Bruno` 一次。 （4）设置 $cnt = cnt + 1$。若 $cnt < Q$，返回步骤（2）；若 $cnt = Q$，进入步骤（5）。 （5）你的程序将被评分。 **重要提示** - 运行时间和内存使用量将根据评分流程中的步骤（1）、（2）、（3）、（4）进行计算。 - 你的程序在步骤（2）中调用函数 `Anna` 或在步骤（3）中调用函数 `Bruno` 时，不得被视为 **Wrong Answer**。你的程序必须在无运行时错误的情况下执行。 - 你的程序可以为内部用途实现其他函数，或使用全局变量。提交的程序将与评分器一起编译，并生成一个单一的可执行文件。所有全局变量和内部函数应声明为 `static`，以避免与其他文件发生冲突。由于在评分时，Anna 和 Bruno 的程序将作为两个独立的进程执行，它们无法共享全局变量。 - 在整个过程中，函数 `Anna` 和 `Bruno` 各自将被调用 $Q = 1000$ 次。你的程序中使用的变量应被适当初始化。 - 你的程序不应使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。 **编译与测试运行** 你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的示例评分器。该归档文件还包含你程序的一个示例源代码文件。 示例评分器由一个源文件组成，该文件为 `grader.c` 或 `grader.cpp`。例如，若你的程序为 `Anna.c` 和 `Bruno.c`，或 `Anna.cpp` 和 `Bruno.cpp`，则你可运行以下命令编译你的程序： - **C** ``` gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm ``` - **C++** ``` g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp ``` 当编译成功后，将生成可执行文件 `grader`。 请注意，实际的评分器与示例评分器不同。示例评分器将以单个进程形式运行，它将从标准输入读取输入数据，并将结果写入标准输出。

示例评分器从标准输入读取以下数据： - 第一行包含一个整数 $Q$。 - 接着，给出 $Q$ 个查询的信息。 - 每个查询的信息由两行组成，具体如下： - 第一行包含三个以空格分隔的整数 $N$、$X$、$K$。这表示待发送序列的长度为 $N$，Anna 要发送的整数为 $X$，且有 $K$ 个损坏位置。 - 第二行包含 $K$ 个以空格分隔的整数 $P_0, P_1, \cdots, P_{K-1}$。这意味着，对于每个 $i$（$0 \le i \le K - 1$），序列中第 $P_i$ 个位置是损坏的

当程序成功终止时，示例评分器将以下信息写入标准输出。（引号本身不会被实际输出。） - 若你的程序被视为 **Wrong Answer**，示例评分器将以如下格式输出其类型：“Wrong Answer [1]”，随后你的程序将被终止。 - 若每次对函数 `Anna` 的调用均未被视为 **Wrong Answer**，示例评分器将输出 “Accepted” 及值 $L^*$。关于 $L^*$ 的取值，请参见“评分”部分。 若你的程序被视为多种类型的 **Wrong Answer**，示例评分器仅报告其中一种。

### 数据范围 所有输入数据均满足以下条件： - $Q = 1000$。 - $N = 150$。 - $0 \le X \le 1\,000\,000\,000\,000\,000\,000$。 - $1 \le K \le 40$。 - $0 \le P_i \le N - 1$（$0 \le i \le K - 1$）。 - $P_i < P_{i+1}$（$0 \le i \le K - 2$）。 ### 评分 - 令 $L^*$ 为本题所有测试用例中以下值的最小值： - 满足条件的最大整数 $L \le 40$，使得对于每个满足 $K \le L$ 的查询，Bruno 均能正确回答出 $X$ 的值。 - 本题的得分按以下方式计算： - 若 $L^* = 0$，得分为 $0$ 分。 - 若 $1 \le L^* \le 14$，得分为 $8$ 分。 - 若 $15 \le L^* \le 37$，得分为 $(L^* - 15) \times 2 + 41$ 分。 - 若 $38 \le L^* \le 40$，得分为 $(L^* - 38) \times 5 + 90$ 分。