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

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

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

本题不支持 hack。

下载

样例及测评库下载