题目描述

译自 JOI Open 2021 T3 「モンスターゲーム / Monster Game」

一个新游戏正在销售中。在这个游戏的世界中，有 $N$ 个怪兽，编号为 $0$ 到 $N-1$。每个怪兽都有个整数的力量值。第 $i\ (0\le i\le N-1)$ 个怪兽的力量值为 $S_i$。力量值满足以下条件。

• 每个怪兽的力量值是一个 $0$ 到 $N-1$ 之间的整数（包括两端）。
• 没有任何两个不同的怪兽有相同的力量值。

你可以选择两个怪兽然后让他们打架。如果怪兽 $a$ 和怪兽 $b$ 打架（$0\le a,b\le N-1,a\neq b$），结果按如下方式确定。

• 如果 $|S_a-S_b|=1$，则力量值小的怪兽获胜。
• 如果 $|S_a-S_b|>1$，则力量值大的怪兽获胜。

忽略打架的结果，你可以让相同的怪兽打任意多次架。

一开始，你不知道怪兽的力量值。你想要知道每个怪兽的力量值。为了达到这个目的，你可以让怪兽之间打至多 $25\ 000$ 次架，并且你会知道每次打架的结果。此外，你想最小化打架的次数。

给出怪兽的数量，写一个程序通过让怪兽打架计算每个怪兽的力量值。

实现细节

你需要在程序中包含 monster.h 头文件。程序需要实现以下函数。

• $\texttt{std::vector<int> Solve(int N)}$

  对于每组数据，这个函数恰好被调用一次。

  • 参数 $\texttt N$ 是怪兽的数量 $N$。
  • 这个函数返回描述每个怪兽的力量值的数组。接下来，令 $\texttt T$ 表示函数返回的数组。
  • $\texttt T$ 的长度应为 $N$。如果条件不满足，你的程序会被判为 Wrong Answer [1]。
  • $\texttt T$ 中每个元素应该都在 $0$ 到 $N-1$ 之间（包括两端）。如果条件不满足，你的程序会被判为 Wrong Answer [2]。
  • 对于每个 $i\ (0\le i\le N-1)$，等式 $\texttt{T[i]}=S_i$ 应被满足。如果条件不满足，你的程序会被判为 Wrong Answer [3]。

你的程序可以调用如下函数、

• $\texttt{bool Query(int a, int b)}$

  使用这个函数，你可以让两个怪兽打架

  • 参数 $\texttt a$ 和 $\texttt b$ 是将要打架的怪兽下标 $a$ 和 $b$。
  • 这个函数会返回打架的结果。如果怪兽 $a$ 赢了，则返回 $\texttt{true}$，否则返回 $\texttt{false}$。
  • 不等式 $0\le a\le N-1$ 和 $0\le b\le N-1$ 需被满足。如果条件不满足，你的程序会被判为 Wrong Answer [4]。
  • 需要满足 $a\neq b$。如果条件不满足，你的程序会被判为 Wrong Answer [5]。
  • 函数 $\texttt{Query}$ 不能调用超过 $25\ 000$ 次。如果条件不满足，你的程序会被判为 Wrong Answer [6]。

交互器输入

第一行一个整数 $N$。

第二行 $N$ 个整数 $S_0,S_1,\ldots, S_{N-1}$。

交互器输出

当程序成功停止时，样例交互器会向标准输出输出以下信息。

• 如果你的程序被判为正确，交互器会输出形如 Accept: 100 的信息，其中 $100$ 是 $\texttt{Query}$ 函数调用的次数。
• 如果你的程序被判为错误，交互器会输出形如 Wrong Answer [1] 的信息。

如果程序中有多种错误之处，样例交互器只会报告其中的一种。

交互器注意事项

对于一些测试点，实际采用的评分器是适应性的。也就是说实际的评分器一开始并没有一个确定的答案，它会根据 $\texttt{Query}$ 之前的调用来做出响应。此处保证至少有一组答案符合所有的响应。

提交注意事项

提交本题时，应当使用 GNU C++ 17 标准，否则会出现编译错误。

样例交互

样例输入

5
3 1 4 2 0

样例交互过程

函数调用	返回值	函数调用	返回值
$\texttt{Solve(5)}$
		$\texttt{Query(1, 0)}$	$\texttt{false}$
		$\texttt{Query(4, 0)}$	$\texttt{false}$
		$\texttt{Query(1, 3)}$	$\texttt{true}$
	$\texttt{[3, 1, 4, 2, 0]}$

数据范围与提示

对于全部数据，满足：

• $4\le N\le 10^3$
• $0\le S_i\le N-1\ (0\le i\le N-1)$
• $S_i\neq S_j\ (0\le i<j\le N-1)$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N\le 200$	$10$
$2$	实际使用的评分器不是适应性的	$15$
$3$	无附加限制	$75$

对于子任务 $3$，如果你的程序正确通过了所有测试数据，你的得分按如下方式计算。

• 令 $X$ 为在这个子任务中所有测试点调用 $\texttt{Query}$ 函数次数的最大值。
• 你的得分按如下方式计算
  • 如果 $10\ 000<X\le 25\ 000$，你的得分为 $\left[75\times \frac{25\ 000-X}{15\ 000}\right]$ 分。
  • 如果 $X\le 10\ 000$，你的得分为 $75$ 分。