题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Zera i jedynki

有一个由 $0$ 和 $1$ 组成的未知序列 $a_{0}, \ldots, a_{n-1}$，你无法直接知道它每个元素的值，但可以通过询问任意两个不同元素之和来推测这个序列。你的任务是用尽量少的询问次数猜出整个序列。

交互方式

请你编写一个程序，利用提供的库来猜出这个 $0$ 和 $1$ 的序列。库会回答你的询问。为了使用这个库，你的程序需要包含以下代码：

• C/C++: #include "zerlib.h"
• Python: from zerlib import daj_n, suma, odpowiedz

库提供了以下函数：

• daj_n()：返回一个整数 $n$，表示未知序列的长度。

• suma(i, j)：返回 $a_{i}+a_{j}$，要求 $0 \leq i, j < n$ 且 $i \neq j$，否则调用会导致错误答案。

• odpowiedz(a)：用于提交你的结果序列，必须且只能调用一次。

  该函数接受一个数组 a[0..n-1]（在 C++ 中为 std::vector<int>，在 Python 中为列表），表示你猜测的序列 $a[0], \ldots, a[n-1]$。调用后，程序会自动终止。如果提交的序列错误或长度不等于 $n$，将被判为错误答案。

注意：库不一定在交互开始时就固定序列 $a_{0}, \ldots, a_{n-1}$，它可能在交互过程中动态调整序列元素，但会保证调整后的序列与之前 suma 的返回结果一致。

你的程序不得打开任何文件或使用标准输入输出，但可以使用标准错误输出（stderr），不过这会消耗运行时间。

程序将与库一起编译，命令如下：

• C++: g++ -O3 -static -std=c++17 zerlib.cpp zer.cpp
• Python: python3 zer.py

提示：内存限制仅针对你的程序，不包括库的内存使用。

示例评测程序

示例评测程序和交互库位于「文件」中。这些库的行为可能与最终评测库不同，且未必符合任务条件，仅用于展示与程序的交互方式。

用示例库编译的程序会从标准输入读取序列描述（$n$ 和 $a_{0}, \ldots, a_{n-1}$，以空格分隔），然后根据这些值回答你的 suma 询问，最后将 odpowiedz 提交的序列输出到标准输出。

样例 1

以下是一个样例的程序运行示例：

样例 2

见附加文件下 [zer1ocen.in](file:zer1ocen.in) 和 [zer1ocen.out](file:zer1ocen.out)。

该样例满足 $n=1000, a=0^{500}1^{500}$（前 $500$ 个 $0$，后 $500$ 个 $1$）；

样例 3

见附加文件下 [zer2ocen.in](file:zer2ocen.in) 和 [zer2ocen.out](file:zer2ocen.out)。

该样例满足 $n=200000, a=(01)^{100000}$（$01$ 重复 $100000$ 次）。

数据范围与提示

详细子任务附加限制及分值如下表所示。

设 $m$ 为你的程序在单个测试点中调用 suma 的最大次数，你的得分将按以下规则计算（若超过时间限制一半，则按比例缩减）：