【MX-X8-T6】「TAOI-3」俄罗斯蓝猫

由于洛谷有特殊的交互题机制，你不需要也不应该在文件开头包含 `kiwi.h`，而是把以下语句复制在文件开头： ```cpp #include<vector> std::vector<long long> game(int n); std::vector<long long> ask(std::vector<int> x,std::vector<int> y); ``` --- 小千绘莉想和你玩游戏！

小千藏有 $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`。你可以通过在代码开头加入下面语句实现： ```cpp #include"kiwi.h" ``` 你需要实现以下函数： ```cpp std::vector<long long> game(int n); ``` 其中 $n$ 表示随机数的数量。 这个函数应当返回一个长度为 $n$ 的数组，表示你求出的数组 $a_i$。 你可以调用如下函数： ```cpp 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$ 长度的限制下，交互库占用资源不超过 $2$ 秒和 $16$ MiB。 下发 `grader.cpp` 为参考交互库，和最终的交互库有所不同。你的做法不应该依赖于交互库实现。 下发 `kiwi.cpp` 为参考实现，你可以通过以下语句来编译你的代码： ```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 分）：$n=5$。 - 测试点 2（30 分）：$n=50$。 - 测试点 3（40 分）：$n=500$。