题目背景

小千绘莉想和你玩游戏！

题目描述

小千藏有 $n$ 个在 $[0,10^{18}]$ 中间随机生成的非负整数 $a_0,a_1,\dots,a_{n-1}$。

你一组询问可以向小千给出不超过 $2n$ 个二元组 $(x_0,y_0),(x_1,y_1),\dots,(x_{m-1},y_{m-1})$，假设 $b_i=a_{x_i}+a_{y_i}$，小千会告诉你 $b_0,b_1,\dots,b_{m-1}$ 从小到大排序后的结果。

你可以向小千提出不超过 $n$ 组询问，你需要按顺序返回 $a_0,a_1,\dots,a_{n-1}$。

需要注意的是：

• 如果你一次询问提出大于 $2n$ 个二元组，或者提出了大于 $n$ 次询问，你会获得 $0$ 分。
• 小千不喜欢重复，如果你某次询问的某个二元组有 $x_i=y_i$，或者有某个无序对 $(x_i,y_i)$ 被询问了多次（在一组询问间或两组不同的询问之间）。小千都会扣除部分分数。
• 具体评分标准见下面【评分标准】。
• 请不要在标准输出输出任何内容。否则视为攻击交互库。会被判定为 Wrong Answer。

输入格式

你不需要，也不应该实现 main 函数。

你需要保证你的文件包含了 kiwi.h。你可以通过在代码开头加入下面语句实现：

#include"kiwi.h"

你需要实现以下函数：

std::vector<long long> game(int n);

其中 $n$ 表示随机数的数量。

这个函数应当返回一个长度为 $n$ 的数组，表示你求出的数组 $a_i$。

你可以调用如下函数：

std::vector<long long> ask(std::vector<int> x,std::vector<int> y);

• 你需要保证 $x,y$ 序列长度相同；
• 该函数会返回和 $x,y$ 长度相等的序列表示 $a_{x_i}+a_{y_i}$ 从小到大排序后的结果。

保证在题目给定的询问次数和 $x,y$ 长度的限制下，交互库占用资源不超过 $3$ 秒和 $16$ MiB。

下发 grader.cpp 为参考交互库，和最终的交互库有所不同。你的做法不应该依赖于交互库实现。

下发 kiwi.cpp 为参考实现，你可以通过以下语句来编译你的代码：

g++ grader.cpp kiwi.cpp -o kiwi -O2 -std=c++14 -static

对编译出来的程序，你只需要输入三个正整数 $T,n,R$ 分别表示数据组组数，每组数据的 $n$ 和随机种子。

实际的交互库中，随机数种子随时间变化。也就是两次不同时间的提交，答案是不同的。

输出格式

输入完成后，交互库会调用 $T$ 次函数 game。每次调用结束后会向标准输出输出以下信息：

• Wrong Answer[1] 表示你某次调用 ask 函数中 $x,y$ 长度不相同；
• Wrong Answer[2] 表示你某次调用 ask 函数中 $x,y$ 长度大于 $2n$；
• Wrong Answer[3] 表示你某次调用 ask 函数中 $x_i,y_i$ 的元素不在 $[0,n-1]$ 内；
• Wrong Answer[4] 表示你本次 game 中调用了超过 $n$ 次 ask；
• Wrong Answer[5] 表示你本次调用 game 函数返回序列的长度不是 $n$；
• Wrong Answer[6] 表示你返回了错误的答案；
• OK, you can get p points. 表示你返回了正确的答案，并且获得了这个测试点 $p\%$ 的分数。评分标准见下面说明。

如果你的代码同时违反了多个规定，只会显示一个，且此时程序会立刻停止。

评分标准

本题首先会受到和传统相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。

假设该测试点满分为 $P$。

• 如果你违反了上述 Wrong Answer 的规则，或者在标准输出中输出了内容，会直接得 $0$ 分。
• 如果你某次调用 ask 时 $x_i=y_i$ 则 $C_1=0.8$，否则 $C_1=1$；
• 如果你调用 ask 时，询问了两组相同的 $\{x_i,y_i\}$ 则 $C_2=0.7$，否则 $C_2=1$；
• 假设你一共调用了 $A$ 次 ask，则：
  • 如果 $0\leq A\leq 2$，则 $C_3=1$；
  • 如果 $A=3$，则 $C_3=0.8$；
  • 如果 $A=4$，则 $C_3=0.6$；
  • 如果 $5\leq A\leq 10$，则 $C_3=0.4$；
  • 如果 $11\leq A$，则 $C_3=0.2$。
• 假设你调用 ask 时，$x$ 数组的最大长度为 $B$，则：
  • 如果 $1\leq B\leq n-1$，则 $C_4=1$；
  • 如果 $B=n$，则 $C_4=0.9$；
  • 如果 $B=n+1$，则 $C_4=0.8$；
  • 如果 $B=n+2$，则 $C_4=0.7$；
  • 如果 $n+3\leq B\leq n+20$，则 $C_4=0.6$；
  • 如果 $n+21\leq B$，则 $C_4=0.5$。

本测试点的最终得分为所有 game 函数，$P\times C_1\times C_2\times C_3\times C_4$ 最小值向下取整。

数据范围

对所有数据，满足 $T=20$，$5\leq n\leq 500$。

• 测试点 1（30 pts）：$n=5$。
• 测试点 2（30 pts）：$n=50$。
• 测试点 3（40 pts）：$n=500$。

下发文件

点击 kiwi.zip 下载文件。