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$ 分。