QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100 Interactive

#10372. 小修和小栋猜♂数字

Statistics

这是一道交互题

小修和小栋喜欢玩一个叫做猜数字的游戏。

小修会先在心中想好一个包含 $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$ 不进行调用,表示你不能还原出这个下标上的值。

实现方法

源代码中需要包含头文件 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。按照上文中提到的方式进行编译,即能通过编译得到可执行程序。

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

输入格式

输出格式

样例数据

样例输入 1

3
1 2 3

样例输出 1

1 2 3
Count: 1

样例解释 1

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

子任务

对于每个测试点,我们将会用你的运行结果与标程的运行结果进行比较,如果还原出来的数列不一致,你将获得 0 分。否则令你和标程调用函数 ask() 的次数分布为 $Y$ 和 $S$,若 $Y \leq S$ 则你的得分比例为 $100\%$,否则你的得分比例为 $(10 \cdot 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 与下发的文件并不一致。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.