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

内存限制:512 MiB 时间限制:4000 ms 题目类型:交互
上传者: samzhang

题目描述

这是一道交互题

小修和小栋喜欢玩一个叫做猜数字的游戏。 小修会先在心中想好一个包含 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():

void guess(int n);

函数 ask() 的接口信息如下:

int ask(int x,int y,int z);

函数 answer() 的接口信息如下:

void answer(int x,int v);

如何测试你的程序

你需要在本题目录下使用如下命令编译得到可执行程序:

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: cntcnt 为你调用函数 ask() 的次数。

样例源代码

在本题目录下,有 C++ 语言的样例源代码 guess.cpp。按照上文中提到的方式进行编译,即能通过编译得到可执行程序。

样例源代码只是帮助理解题目,结果不一定正确

其他语言

C/C++ 以外的语言可以通过标准输入输出进行交互。

程序开始时,从标准输入读入一行,包含正整数 n

此后,需要调用 ask() 时,向标准输出输出一行 Ask <x> <y> <z> 并刷新输出缓冲(例如 Pascal 语言的 flush(output) 和 Java 语言的 System.out.flush(),其他语言请参阅语言文档);此后从标准输入读入一行,包含一个整数,表示询问结果。

需要调用 answer() 时,向标准输出输出一行 Answer <x> <v> 并刷新输出缓冲。

程序结束时输出一行 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 与下发的文件并不一致。