题目描述

这是一道交互题。

有一个长为 $n$ 的序列 $a_0, a_1, \dots, a_{n-1}$，其中每个 $a_i$ 都是 $0$ 或 $1$。保证序列中存在至少一个 $1$。

你不知道这个序列。为了确定这个序列的具体值，你可以进行下面这种测试：

• 选择一个下标集合 $U = \{0, 1, \dots, n - 1\}$ 的子集 $S$，没选中的元素集合 $T = U \setminus S$。你可以知道 $S$ 和 $T$ 哪一个包含的 $a_i = 1$ 数量更多，或者两个集合的 $a_i = 1$ 数量相等。

实现细节

你需要实现以下过程：

std::vector<int> solve(int n)

• $n$ 是序列长度。
• 这个过程需要返回一个数组 $a$，表示你确定的序列。
• 这个过程在每组测试点会被调用至多 $10^4$ 次。

上述过程可以调用以下过程：

int query(std::vector<int> V)

• $V$ 表示你测试的下标集合 $S$。$V$ 包含 $|S|$ 个元素，依次对应 $S$ 中的元素。
• 这个过程返回：
  • $1$：如果 $S$ 包含的 $1$ 比 $U \setminus S$ 多；
  • $0$：如果 $S$ 包含的 $1$ 与 $U \setminus S$ 相等；
  • $-1$：如果 $S$ 包含的 $1$ 比 $U \setminus S$ 少；
• 在每组测试数据中，这个过程最多能被调用 $32$ 次。

交互库不自适应。

样例

样例输入 1

1
4
0 0 1 0

样例输出 1

0 0 1 0
3

说明

solve 可能会按如下方式调用 query：

1. query([0]) 返回 $-1$，因为这个集合存在 $0$ 个 $1$，不在这个集合的有 $1$ 个 $1$。
2. query([1, 2]) 返回 $1$。
3. query([2]) 返回 $1$。

通过以上询问的结果，可以唯一确定这个序列是 $[0, 0, 1, 0]$。

数据范围

$2 \le n \le 16$。

子任务

1. (20 分) $n = 2$
2. (20 分) $n = 4$
3. (40 分) 序列中 $1$ 的数量是奇数。
4. (20 分) 没有附加限制。

如果任何测试数据中对 solve 的调用不符合“实现细节”中描述的约束，或者 solve 的返回值不正确，则该测试点的得分将为 $0$。

在每个子任务中，你可以获得部分分数。设 $q$ 为一次调用 solve 时，你调用 query 次数的最大值，你可以获得该子任务得分的相应百分比：

$$\min\left(5 \cdot e^{\ln 20 \cdot \frac{(32 - q)}{14}}, 100\right) \%$$

你在一组子任务的得分是所有测试点得分的最小值，最终将会被下取整。

样例评测程序

样例评测程序按以下格式读取输入：

第 1 行：$t$，表示调用 solve 的次数。

接下来 $t$ 次输入，每次输入两行：

第 1 行：$n$
第 2 行：$a_0\ a_1\ \dots\ a_{n - 1}$

在调用 solve 之前，样例评测程序会检查是否至少有一个 $1$。如果不满足此条件，它将打印消息 No 1 in the sequence 并终止整个程序。

如果你调用 query 时：

• 数组 $V$ 包含大于 $n$ 个元素，或
• 存在元素不是 $0$ 到 $n - 1$ 之间的整数，或
• 包含重复元素

输出将为 Protocol Violation: invalid array。

如果你调用 query 的次数超过 $32$ 次，输出将为 Protocol Violation: too many calls。

否则，设你的 solve 返回的数组元素是 $c_0, c_1, \dots, c_{n - 1}$，对于这次调用，样例评测程序按以下格式输出：

第 1 行：$a_0\ a_1\ \dots\ a_{n - 1}$。
第 2 行：调用 query 的次数。