存在一个由 $0$ 和 $1$ 组成的序列 $a_0, \dots, a_{n-1}$。你不知道这个序列，但你可以询问序列中任意两个不同元素的和。你的任务是通过尽可能少的问题猜出该序列。
交互
实现一个程序，利用提供的库来回答提出的问题，从而猜出该 $01$ 序列。要使用该库，需要在你的程序中包含：
- C/C++:
#include “zerlib.h” - Python:
from zerlib import daj_n, suma, odpowiedz
该库提供以下函数：
daj_n()– 该函数返回一个整数 $n$，表示未知 $01$ 序列的长度。suma(i, j)– 该函数返回 $a_i + a_j$ 的结果，其中 $0 \le i, j < n$ 且 $i \neq j$。否则，调用该函数会导致错误回答。odpowiedz(a)– 该函数允许你提交最终的序列。必须且只能调用一次。它接受一个数组 $a[0..n-1]$（在 C++ 中为std::vector<int>，在 Python 中为列表），表示结果序列 $a_0, \dots, a_{n-1}$。调用此函数后，程序将自动终止。如果函数中提供的序列错误或其长度不等于 $n$，将导致错误回答。
库不需要在与你的程序交互开始时就生成序列 $a_0, \dots, a_{n-1}$。它可以在交互过程中更改序列的元素，只要新元素与之前调用 suma 函数返回的结果保持一致即可。
你的程序不得打开任何文件或使用标准输入输出。它可以使用标准错误输出 (stderr)，但请记住，这会消耗宝贵的时间。
你的解决方案将通过以下命令与库一起编译：
- C++:
g++ -O3 -static -std=c++17 zerlib.cpp zer.cpp - Python:
python3 zer.py
注意：上述内存限制仅适用于你的解决方案，不包括库所使用的内存。
子任务
测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。
| 子任务 | 条件 | 分数 |
|---|---|---|
| 1 | $3 \le n \le 1000$ | 50 |
| 2 | $3 \le n \le 200\,000$ | 50 |
如果 $m$ 是你的程序在单个测试用例中调用 suma 函数的最大次数，则你的解决方案将获得该测试用例的以下百分比分数（如果超过时间限制的一半，则相应缩放）：
| 调用次数 | 测试得分百分比 |
|---|---|
| $m \le n$ | 100% |
| $m = n + 1$ | 80% |
| $m \le n^2 - n$ | 50% |
| $m > n^2 - n$ | 0% (判决：错误回答) |
样例
样例程序运行过程
下表展示了样例测试的程序运行过程。
| 调用 | 结果 | 说明 |
|---|---|---|
daj_n |
5 | $n = 5$ |
suma(0, 1) |
1 | $a_0 + a_1 = 1$ |
suma(1, 2) |
1 | $a_1 + a_2 = 1$ |
suma(3, 4) |
2 | $a_3 + a_4 = 2$, 因此 $a_3 = a_4 = 1$ |
suma(0, 3) |
2 | $a_0 + a_3 = 2$, 因此 $a_0 = 1$, 由此得出 $a_1 = 0$ 且 $a_2 = 1$ |
odpowiedz({1,0,1,1,1}) |
– | 使用 $m = 4 \le n = 5$ 次询问的正确回答，100% 测试得分 |
“评分”测试： 1. $n = 1000, a = 0^{500}1^{500}$ 2. $n = 200\,000, a = (01)^{100\,000}$
实现细节
示例错误解决方案及示例库位于 dlazaw 文件夹中。库的行为可能与最终评分所用的库不同，且可能不满足题目要求。它们仅用于展示与程序的交互方式。
你的解决方案与示例库编译后，会从标准输入读取序列描述——数字 $n$，随后是空格分隔的数字 $a_0, \dots, a_{n-1}$——然后使用它们来回答你程序中的 suma 问题，最后将 odpowiedz 函数中传递的序列输出到标准输出。