P7805 [JOI Open 2021] 怪兽游戏 / Monster Game

**本题为交互题。** 交互库与 spj 提供者 @[Liking_Cpp_In_Luogu](https://www.luogu.com.cn/user/705620)，感谢他的贡献！ 请不要在代码中加入头文件 `monster.h`，在 Solve 函数前加上 `extern "C"`，开头加上 `extern "C" bool Query(int,int);` 即可。

你圈养了 $N$ 只书虫，这 $N$ 只书虫编号为 $0 \sim N-1$，第 $i$ 只书虫的力量值为 $S_i$，满足 $S_i \in [0,N-1]$，且没有两只书虫的力量值是相等的。 你可以调用最多 $25000$ 次「打架事件」： - 选择两只编号不相同的书虫 $a,b$： - 如果 $|S_a-S_b|=1$，则力量值小的书虫获胜； - 如果 $|S_a-S_b|>1$，则力量值大的书虫获胜。 请最小化调用「打架事件」的次数，你可以得到每次「打架事件」的结果，求所有书虫的力量值。 #### 交互格式 你的程序需要实现以下函数： - `std::vector Solve(int N)` - 对于每组数据，该函数只能被调用一次； - $N$：书虫的个数； - 该函数返回这 $N$ 只书虫的力量值数组 $T$； - 应该满足 $|T|=N$，否则您的程序将会被判为 `Wrong Answer [1]`； - 应该满足 $T_i\in [0,N-1]$，否则您的程序将会被判为 `Wrong Answer [2]`； - 应该满足 $T_i=S_i$，否则您的程序将会被判为 `Wrong Answer [3]`。 你的程序可以调用以下函数： - `bool Query(int a, int b)` - 你可以用这个函数调用「打架事件」； - $a,b$：书虫 $a$ 与书虫 $b$ 打架； - 如果 $a$ 获胜了，则返回 `true` 否则返回 `false`； - 应该满足 $a \in [0,N-1]\land b \in [0,N-1]$，否则您的程序将会被判为 `Wrong Answer [4]`； - 应该满足 $a \ne b$，否则您的程序将会被判为 `Wrong Answer [5]`； - 调用 `Query` 函数应该不超过 $25000$ 次。否则您的程序将会被判为 `Wrong Answer [6]`。 **特殊说明** 1. 您的程序可以调用其他标准库里的函数，或者使用全局变量； 2. 您的程序不得使用标准输入与标准输出。

见「交互格式」。

见「交互格式」。

#### 样例 1 解释 样例的交互过程： |调用|返回|调用|返回| |:-:|:-:|:-:|:-:| |`Solve(5)`|||| |||`Query(1, 0)`|`false`| |||`Query(4, 0)`|`false`| |||`Query(1, 3)`|`true`| ||`[3, 1, 4, 2, 0]`|| #### 评测程序示例（样例） 评测程序示例以如下格式读取输⼊数据： 第一行：$N$ 第二行：$S_0\ S_1\ \cdots\ S_{N-1}$ 评测程序示例以如下格式读取输出数据： 当程序成功结束运行后，样例交互器会在标准输出中输出以下内容： - 如果你的程序被判为正确，样例交互器会输出类似 `Accepted: 100` 的信息，其中 $100$ 为你的程序调用 `Query` 函数的次数； - 如果你的程序被判为错误，样例交互器的输出内容已在「交互格式」中描述。 如果你的程序有多数错误，样例交互器只会判断其中的一种。 注意，交互器在某些数据中是自适应性的，也就是实际的交互器刚开始并没有一个确定的答案，而是会随着之前 `Query` 函数的调用逐渐做出响应，能保证至少有一组答案满足交互库做出的响应。 （本来原题有一个工具可以用来检测，但是找不到检测文件了，所以就咕掉了） #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（10 pts）：$N \le 200$； - Subtask 2（15 pts）：实际使用的交互库并不是自适应性的； - Subtask 3（75 pts）：无特殊限制。 对于 $100\%$ 的数据： - $4 \le N \le 1000$； - $0 \le S_i \le N-1$； - $S_i$ 保证互不相同。 对于 Subtask 3，特有一套评分标准： 如果你的程序通过了所有测试数据，那： - 设 $X$ 为 Subtask 3 中你的程序对每个测试点调用的 `Query` 函数的次数的最大值； - 你的分数将按照下面的过程计算： - 如果 $10^4