2489 「2018 集训队互测 Day 4」小修和小栋猜♂数字

内存限制:512 MB 时间限制:4000 ms

题目描述

这是一道**交互题**。 小修和小栋喜欢玩一个叫做猜数字的游戏。 小修会先在心中想好一个包含 $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++ 提供函数接口。其他语言请使用标准输入/输出进行交互。 源代码中需要包含头文件 `guess.h`。 你需要实现的函数 `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 ``` 可执行文件将从**标准输入**读取以下格式的数据: 第一行包含一个正整数 $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()` 的次数。 ### 样例源代码 在本题目录下,有 C++ 语言的样例源代码 `guess.cpp`。按照上文中提到的方式进行编译,即能通过编译得到可执行程序。 样例源代码只是帮助理解题目,结果**不一定正确**。 ### 其他语言 C/C++ 以外的语言可以通过标准输入输出进行交互。 程序开始时,从标准输入读入一行,包含正整数 $n$。 此后,需要调用 `ask()` 时,向标准输出输出一行 `Ask ` 并刷新输出缓冲(例如 Pascal 语言的 `flush(output)` 和 Java 语言的 `System.out.flush()`,其他语言请参阅语言文档);此后从标准输入读入一行,包含一个整数,表示询问结果。 需要调用 `answer()` 时,向标准输出输出一行 `Answer ` 并刷新输出缓冲。 程序结束时输出一行 `Finish` 并退出。 所有输出同样需要满足上述限制。

样例

样例输入 1

3
1 2 3

样例输出 1

1 2 3
Count: 1

样例解释 1

这是使用试题目录的 grader 和样例源程序得到的输出文件。

样例输入 2

见「附加文件」中的 guess2.in。

数据范围与提示

对于每个测试点,我们将会用你的运行结果与标程的运行结果进行比较,如果还原出来的数列不一致,你将获得 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 与下发的文件并不一致。