[APIO2017] 考拉的游戏

### 特别提示 **在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：** 1. 提交时请在程序里加入以下函数声明语句： ```cpp void playRound(int*,int*); ``` 2. 程序开头不用，也不应该包含 `koala.h` 头文件。 3. 仅支持 `C++`（含 `C++`，`C++11`，`C++14`，`C++17`）提交。

Koala 发明了一个新游戏，来邀请你一起玩！游戏的开始，她会在桌上放 $N$ 个物品，物品从 $0$ 到 $N - 1$ 标号。接着，她会秘密地给每个物品分配一个 $1$ 到 $N$ 之间的整数权值，且任意两个物品不会被分配到相同的权值。其中，第 $i$ 个物品的权值为 $P_i$。她请你来确定由这些权值构成的序列 $P=P_0,P_1,\dots ,P_{N-1}$ 的一些特征。 为了回答她的问题，你可以请 Koala 玩若干轮游戏。每一轮中，你会得到 $W$ 个蓝色石子，Koala 会得到 $W$ 个红色石子。首先，你可以选择若干个物品，再把你的一些（或全部）石子放在这些物品的旁边。Koala 会观察你的石子分配，然后类似地把她的一些（或全部）石子放在若干个物品旁边。如果一个物品旁边的红色石子数严格大于蓝色石子数，那么，Koala可以获得这个物品。Koala 分配她的石子时，总会选择使她获得的物品的权值和最大的方案，如果有多种方案可以做到这一点，她会选择一种获得的物品数最多的方案，如果仍然有多种方案，她会选择其中任意一种。 Koala 非常懒，如果你和她玩太多轮游戏，她就会睡着。你的任务是通过尽可能少轮数的游戏，确定 Koala 的序列 $P$ 的相关特征。 ### 任务 在这个任务中，你需要实现 $4$ 个函数：`minValue`, `maxValue`, `greaterValue` 和 `allValues`。 每个函数需要你确定序列 $P$ 的不同特征。我们强烈推荐在我们提供的模版的基础上进行作答。注意，即使你只想获得部分子任务的分数，你也必须为四个函数都提供一个实现（尽管一些函数的内部可能为空）。你的程序禁止从标准输入读数据、向标准输出写数据或与任何文件交互。 在每个函数中，参数 `N` 表示游戏中物品的个数，参数 `W` 表示你和 Koala 在每一轮游戏中拥有的石子数。 * `minValue(N, W)` --- 这个函数需要返回权值最小的物品的标号 $i$，即 $P_i=1$ * `maxValue(N, W)` --- 这个函数需要返回权值最大的物品的标号 $i$，即 $P_i=N$ * `greaterValue(N, W)` --- 这个函数需要比较物品 $0$ 和物品 $1$ 的权值，返回权值较大的物品的标号。具体来说，若 $P_0>P_1$​，它应该返回 $0$ ，否则返回 $1$ 。 * `allValues(N, W, P)` --- 这个函数需要确定整个排列，并将其存放在给定的数组 $P$ 中：具体来说，$P[i]$ 应该保存物品 $i$ 的权值 $P_i (0 \leq i \leq N-1)$。 在每个测试点中，交互库会一次或多次调用这些函数中的一个。每次函数调用代表不同的任务，哪个函数会被调用、以及最多被调用多少次取决于子任务（见下文）。你可以认为 Koala 在每次函数调用前确定了她的序列 $P$，并且序列不会在一次函数的调用过程中改变。一次调用结束后，她可以在下次函数调用之前改变她的序列。 你实现的四个函数可以通过调用函数 `playRound` 来获取 Koala 的序列的相关信息。 * `playRound(B, R)`，请 Koala 和你玩一轮游戏。 数组 `B` 描述你在每个物品旁边放了多少蓝色石子。具体来说，对任意 $0 \leq i \leq N-1$，$B[i]$ 个蓝色石子将会被放在物品 $i$ 旁边。每个 $B[i]$ 必须是一个非负整数，且 $B[0]+B[1]+\cdots +B[N-1]$ 不能超过 $W$ 。 交互库会把 Koala 的回应存放在你提供的数组 `R` 中。具体来说，对任意 $0 \leq i \leq N-1$，Koala 会在物品 $i$ 旁边放 $R[i]$ 个红色石子。 每个子任务对你在每次游戏中调用 `playRound` 的次数有所限制。注意，调用次数越少你的得分可能会越高。（具体限制和评分方式参见下文）

### 子任务 #### 样例数据：$0$ 分 **因为特殊原因（不支持设置 $0$ 分测试点），评测时将不测样例**。 * 有 $5$ 个「样例数据」测试点，每个测试点恰好调用一次 $4$ 个函数中的某一个。请看下文的「样例」获取各测试点的详细信息。 * $N=6$ * $P=5,3,2,1,6,4$ 每次游戏中，你可以调用 `playRound `至多 $3200$ 次。 #### 子任务 1：$4$ 分 * 在这个子任务中，交互库只会调用函数 `minValue`，每个测试点中，这个函数最多会被调用 $100$ 次。 * $N=100$ * $W=100$ * 每一次游戏中，你可以调用 `playRound` 至多 $2$ 次。 #### 子任务 2：$15$ 分 * 在这个子任务中，交互库只会调用函数 `maxValue`。每个测试点中，这个函数最多会被调用 $100$ 次。 * $N=100$ * $W=100$ * 每一次游戏中，你可以调用 `playRound` 至多 $13$ 次。 * 这个子任务中，一个测试点的分数取决于每一轮游戏中 `playRound` 被调用次数的最大值 $C_{max}$，具体来说，你的得分为： - 若 $C_{max}\leq 4$，获得 $15$ 分。 - 若 $5 \leq C_{max} \leq 13$，获得 $7$ 分。 #### 子任务 3：$18$ 分 * 在这个子任务中，交互库只会调用函数 `greaterValue`。每个测试点中，这个函数最多会被调用 $1100$ 次。 * $N=100$ * $W=100$ * 每一次游戏中，你可以调用 `playRound` 至多 $14$ 次。 * 这个子任务中，一个测试点的分数取决于每一轮游戏中 `playRound` 被调用次数的最大值 $C_{max}$，具体来说，你的得分为： - 若 $C_{max}\leq 3$，获得 $18$ 分。 - 若 $C_{max}=4$，获得 $14$ 分。 - 若 $C_{max}=5$，获得 $11$ 分。 - 若 $6 \leq C_{max}\leq 14$，获得 $5$ 分。 #### 子任务 4：$10$ 分 * 在这个子任务中，交互库只会调用函数 `allValues`，每个测试点中，这个函数会被调用恰好一次。 * $N=100$ * $W=200$ * 你可以调用 `playRound` 至多 $700$ 次。 #### 子任务 5：$53$ 分 * 在这个子任务中，交互库只会调用函数 `allValues`，每个测试点中，这个函数会被调用恰好一次。 * $N=100$ * $W=100$ * 你可以调用 `playRound` 至多 $3200$ 次。 * 这个子任务中，一个测试点的分数取决于 `playRound` 被调用的次数 $C$ ，具体来说，你的得分为： - 若 $C \leq 100$，获得 $53$ 分。 - 若 $101 \leq C \leq 3200$，获得 $\lfloor 53-8 \log_2 (c/100) \rfloor$ 分。其中，$\lfloor x \rfloor$ 为不大于 $x$ 的最大整数。举例来说，若 $C=3200$，那么你的解答将获得 $13$ 分。 ### 评分方式 - 和传统题一样，你的程序的运行时间和空间不能超过时间和空间限制。**交互库运行的时间和空间也会算入你的程序的总时间和空间当中**。当你估算这一部分的时空消耗时，你可以认为，在评测时使用的交互库与我们提供的样例交互库有**相同的函数**和**相似的实现**。 - 在一个测试点中，若你在调用 `playRound` 时传入了非法的数组 B，或调用 `playRound` 的总次数超过了上限，那么该测试点记 $0$ 分。 - 在一个测试点的任意一次游戏中，若一个函数没有正确地回答所要求的 Koala 的序列的特征，那么该测试点记 $0$ 分。 - 子任务 4 和子任务 5 均要求你实现函数 `allValues`，但在调用时传入了不同的 $W$。你可以利用两个子任务在这个参数上的不同，从而在你的实现中区分两个子任务。你可以参考你的语言的模板实现获取更详细的信息。 - 比赛时，你可以提交本题目最多 60 次，连续两次的提交至少间隔 2 分钟。 - **你在一个子任务上的得分，等于你在该子任务所有测试点中的最低得分**。 ### 如何测试你的程序 在终端下输入如下命令进行编译： ```bash g++ grader.cpp koala.cpp -o grader -g -Wall --std=c++11 ``` 样例交互库将按如下格式从标准输入读入数据： 第一行两个整数 $F,G$，其中 $F$ 代表交互库调用的函数类型，$G$ 代表调用函数的次数； 接下来 $G$ 行，每行开头两个整数 $N,W$，后跟 $N$ 个整数 $P_0,P_1,\ldots,P_{N-1}$。 $F$ 对应的样例交互库调用的函数类型如下表所示： | $F$ | 调用的函数类型 | | ----------- | ----------- | | $1$ | `minValue` | | $2$ | `maxValue` | | $3$ | `greaterValue` | | $4$ | `allValues` | 对于每次函数调用，样例交互库将向标准输出输出两行。第一行代表你调用 `playRound` 的次数，第二行代表函数调用后返回的结构（对于 $F=4$ 的情况，将输出调用 `allValues` 时返回的数组，对于其他情况，将输出函数的返回值）。 ### 样例 考虑如下的排列： | $i$ | 0 | 1 | 2 | 3 | 4 | 5 | | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | | $P_i$ | 5 | 3 | 2 | 1 | 6 | 4 | 下表展示了几次调用函数 `playRound` 的例子，以及交互库对每个调用的有效反馈（注意，一次 `playRound` 的调用，可能会有多种可能的有效反馈） 。 | $W$ | 调用 | 可能的交互库反馈 | 解释 | | ----------- | ----------- | ----------- | ----------- | | 6 | `playRound([0,3,0,2,1,0],R)` | `R=[1,1,1,0,2,1]` | Koala 获得了物品 $0,2,4,5$，总权值为 $17$，这是一种可能的权值最大的方案。 | | 6 | `playRound([1,2,3,1,2,0],R)` | 非法调用 | 你总共放了 $9$ 个石子，超过了 $W$ 的限制。 | | 12 | `playRound([0,3,0,2,1,0],R)` | `R=[2,3,0,2,3,1]` | 你不用放完 $W$ 个石子，Koala 也不用放完 $W$ 个石子。 | | 6 | `playRound([0,1,0,0,1,0],R)` | `R=[1,0,1,1,2,1]` | 若 Koala 有多种方案最大化获得物品的权值，她会选择使自己获得物品最多的方案。因此 `R=[1,2,0,0,2,1]` 不是一个合法的返回值。 | 下面是样例数据的返回值，请注意在样例数据中，你可以调用 `playRound` 至多 $3200$ 次。 | # | 交互库调用 | 期望返回值 | 解释 | | ----------- | ----------- | ----------- | ----------- | | 1 | `minValue(6,6)` | 3 | $P_3=1$ | | 2 | `maxValue(6,6)` | 4 | $P_4=6$ | | 3 | `greaterValue(6,6)` | 0 | $P_0=5,P_1=3$ | | 4 | `allValues(6,12,P)` | `P=[5,3,2,1,6,4]` | 注意 `allValues` 无返回值，而是将正确结果放入 P 中。 | | 5 | `allValues(6,12,P)` | `P=[5,3,2,1,6,4]` | 同上。 | ### 附加文件 附加文件包含样例输入输出，C++ 样例交互库和程序模板，我们推荐您在模板的基础上实现您的程序。