题目背景

特别提示

在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：

1. 提交时请在程序里加入以下函数声明语句：

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 分钟。
• 你在一个子任务上的得分，等于你在该子任务所有测试点中的最低得分。

如何测试你的程序

在终端下输入如下命令进行编译：

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$，这是一种可能的权值最大的方案。
	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			同上。

附加文件

附加文件包含样例输入输出，C++ 样例交互库和程序模板，我们推荐您在模板的基础上实现您的程序。