P14490 [集训队互测 2018] 小修和小栋猜数字

评测时，不要引入头文件。在文件头加入 ```cpp int ask(int,int,int); int answer(int,int); ``` --- 试题来源：，向 LOJ 和出题人表示感谢。如果版权方并不希望试题出现在洛谷，可联系洛谷管理组撤下试题。

这是一道**交互题**。 小修和小栋喜欢玩一个叫做猜数字的游戏。 小修会先在心中想好一个包含 $n$ 个互不相同的正整数的序列 $a_1,a_2,\dots,a_n$。 小栋每次会向小修询问 $a_x,a_y,a_z$ 的中位数，小修会准确地回答。然后小栋则需要利用这些信息来尽可能地还原出序列 $a$。 然而小修实在是太厉害了，选取的 $n$ 都会特别大，导致小栋根本不知如何处理。 请你帮助小栋，让他能和小修愉快地玩耍。 ### 任务介绍 你需要实现一个函数 `guess()`，以帮助小栋完成游戏。 * `guess(n)` * `n` 为序列的长度。 在每个测试点中，交互库都会调用恰好一次 `guess()` 函数。 你可以调用函数 `ask()` 来向小修进行询问。我们会根据你调用这个函数的**总次数**评分。 * `ask(x,y,z)` * `x,y,z` 为三个不同的下标 * 这个函数会返回 $a_x,a_y,a_z$ 的中位数。 同时，你还可以调用函数 `answer()` 来回答你还原出的信息。 * `answer(x,v)` * `x` 为还原出的数的下标 * `v` 为还原出的 $a_x$ 的值 你不能对于同一个 $x$ 进行两次调用，但可以对于某些 $x$ 不进行调用，表示你不能还原出这个下标上的值。 ### 实现方法 本题只对 C/C++ 提供函数接口。 源代码中需要在开头声明函数： ```cpp int ask(int x,int y,int z); void answer(int x,int v); ``` 你需要实现的函数 `guess()`: ```cpp void guess(int n); ``` 函数 `ask()` 的接口信息如下： ```cpp int ask(int x,int y,int z); ``` 函数 `answer()` 的接口信息如下： ```cpp void answer(int x,int v); ``` ### 如何测试你的程序 你需要在本题目录下使用如下命令编译得到可执行程序： ```plain g++ -o guess grader.cpp guess.cpp -O2 ``` ### 样例源代码 在本题目录下，有 C++ 语言的样例源代码 `guess.cpp`。按照上文中提到的方式进行编译，即能通过编译得到可执行程序。 样例源代码只是帮助理解题目，结果**不一定正确**。

可执行文件将从**标准输入**读取以下格式的数据： 第一行包含一个正整数 $n$，需要保证 $n \leq 10^5$。 第二行一共 $n$ 个正整数，$a_1,a_2,\dots,a_n$，需要保证 $a_i$ 互不相同且 $0 < a_i \leq 10^9$。 读入完成之后，交互库将会调用 `guess()` 函数。

接下来交互库将会在**标准输出**中输出以下信息： 第一行一共 $n$ 个正整数，$b_1,b_2,\ldots,b_n$，表示你还原出的序列，$b_i=-1$ 表示你没有还原出该下标上的值。 第二行形如 `Count: cnt`，`cnt` 为你调用函数 `ask()` 的次数。

对于每个测试点，我们将会用你的运行结果与标程的运行结果进行比较，如果还原出来的数列不一致，你将获得 0 分。否则令你和标程调用函数 `ask()` 的次数分布为 $Y$ 和 $S$，若 $Y \leq S$ 则你的得分比例为 $100\%$，否则你的得分比例为 $(10*2^{4-\frac{Y}{S}}+20)\%$。 对于每个子任务，你的得分将是所有测试点的得分取最小值并乘上该子任务分值的结果。 子任务 1（20分）：$n \leq 10$； 子任务 2（20分）：$n \leq 100$； 子任务 3（20分）：$n \leq 2000$； 子任务 4（40分）：$n \leq 100000$。 请注意最终测评使用的 `guess.h` 与下发的文件并不一致。