题目背景

这是一道交互题。

本题只支持 C++ 提交，建议使用 C++17。

提交时不需要包含 haru.h 头文件。

为了确保程序正常编译，你需要在你提交的程序开头加上如下函数声明语句：

std::vector<long long> query(const std::vector<std::vector<int>> &U,const std::vector<std::vector<int>> &V);
bool guess(const std::vector<int> &U, const std::vector<int> &V, long long x);

如遇评测问题，请联系搬题人。

---

走路要注意脚下，不要边走路边玩手机，以防进掉水里；

去外面玩注意天气，不要在雨天荡秋千，以防感冒。

题目描述

这是一道交互题，仅支持 C++ 提交。

紗凪有一个隐藏的正整数数组 $a_0,\dots,a_{n-1}$（$1\leq a_i\leq 10^9$），定义一颗点集为 $0\sim n-1$ 的树 $T$ 的直径 $D(T)$ 为，当我们把第 $i$ 个点附以点权 $a_i$ 时，最大点权和路径的点权和。

你需要在 $2000$ 次查询和 $2000$ 次猜测之内确定至少 $n-2$ 个 $a_i$：

• 查询：询问一棵树 $T$，交互库会返回 $D(T)$。这个询问是离线的，即你要进行完所有查询之后才能知道每次查询的答案。
• 猜测：询问一棵树 $T$ 和正整数 $x$，交互库会返回 $[D(T)=x]$。这个操作询问是在线的，即每次猜测后可以立刻知道结果。

实现细节

你需要引用头文件 haru.h。

你需要实现下面的函数

std::vector<int> haru(int n);

其中 $n$ 表示 $a$ 数组的长度。

这个函数需要返回一个长度为 $n$ 的数组 $b$，其中最多有 $2$ 个 $-1$ 表示你不能确定这个 $a_i$ 的值，其余元素都在 $[1,10^9]$ 之内表示你确定这个 $a_i$ 的值。

这个函数在一个测试点内可能会被调用多次。

你可以调用以下两个函数：

std::vector<long long> query(const std::vector<std::vector<int>> &U,const std::vector<std::vector<int>> &V);

这个函数对应题目描述中的查询，这个函数只能被调用一次。你需要保证 $U,V$ 长度个数相同（记为 $k$），且每个元素都是一个长度为 $n-1$ 的数组，且仅包含 $[0,n-1]$ 之内的整数。

这个函数会返回一个长度为 $k$ 的数组，其中第 $i$ 个数表示考虑 $T$ 由 $(U_{i,j},V_{i,j})$（$0\leq j < n-1$）这些边构成时，$D(T)$ 的值。

bool guess(const std::vector<int> &U, const std::vector<int> &V, long long x);

这个函数对应题目描述中的猜测。你需要保证 $U,V$ 长度都为 $n-1$，且仅包含 $[0,n-1]$ 之内的整数。

这个函数会返回一个 bool 值表示考虑 $T$ 由 $(U_{i},V_{i})$（$0\leq i < n-1$）这些边构成时 $D(T)$ 是否等于 $x$。

你可以查看下发文件中的 grader.cpp，其实现与评测时的交互库几乎一致。

测试程序方式

下发 haru.cpp 是参考实现。你可以在本题目录下使用以下指令来编译你的代码：

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

输入格式

对编译出来的程序，输入格式是：

第一行一个正整数 $T$ 表示测试数据数量。对于每个测试数据：

第一行一个正整数表示 $n$；

第二行一个长度为 $n$ 的正整数数组表示隐藏的 $a_i$。

输出格式

程序会输出得分信息，具体地：

• 如果你的输入不合法、或者调用时违反了某些限制会获得 Wrong Answer[x] 的返回信息，此时程序会立即停止，具体错误见下发 grader。
• 否则，交互库会输出 AC with x query(s) and y guess(es). 表示你在每个测试数据都返回了正确的答案，且调用查询、猜测数量最大值为 $x,y$。

见下发 1.in

见下发 1.ans

提示

本题采用捆绑测试。

子任务编号	$n\leq$	特殊性质	分值
1	$10$	$1 \leq T \leq 10$、$1 \leq a_i \leq 2$	$7$
2	$500$	保证 $a_i$ 互不相同	$24$
3	^	无	$69$

对于所有数据，保证：$10\leq n\leq 500$、$\sum n\leq 5\times 10^4$、$1\leq a_i\leq 10^9$。

评分标准

注意：

• 选手不应该通过非法方式获得交互库的内部信息，如试图访问 $a$ 数组，或者与标准 IO 进行交互，这种行为视为作弊；
• 交互库是非自适应的，即答案在一开始就确定，不会随着询问而改变。

保证在合法情况下，交互库消耗时空分别不超过 1s、64MB。

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

在此基础上，记这个测试点满分为 $T$、询问长度为 $X$、猜测次数为 $Y$。那么这个测试点你可以获得 $\lfloor Tf(X)g(Y) \rfloor$ 分，其中：

$$f(x) = \max\left(0,1-\left(\dfrac{\max(x-501,0)}{1500}\right)^{0.4}\right) $$$$g(x)=\max\left(0,\min\left(1,1.5-\left(\dfrac{\max(x-16,0)}{128}\right)^{0.2}\right)\right) $$

下面是你可能会用到的 $f(x)$ 的单点值：

$x=$	$f(x)=$
$0\sim 501$	$1$
$502$	$0.946351$
$503$	$0.929209$
$504$	$0.916745$
$505$	$0.906591$
$510$	$0.870801$
$520$	$0.825793$
$550$	$0.745527$
$600$	$0.662854$
$800$	$0.475396$
$1000$	$0.356122$
$1500$	$0.150057$
$2000$	$0.00026672$

下面是你可能会用到的 $g(x)$ 的单点值：

$x=$	$g(x)=$
$0\sim 20$	$1$
$21$	$0.97718$
$25$	$0.91196$
$30$	$0.857632$
$40$	$0.784515$
$50$	$0.732897$
$100$	$0.580792$
$200$	$0.42472$
$500$	$0.195251$
$1000$	$0$