P12918 [POI 2021/2022 R3] 0 和 1 / Zera i jedynki【交互库暂未配置】

翻译来自于 [LibreOJ](https://loj.ac/p/4855)。

**题目译自 [XXIX Olimpiada Informatyczna – III etap](https://sio2.mimuw.edu.pl/c/oi29-3/dashboard/) [Zera i jedynki](https://szkopul.edu.pl/problemset/problem/O8s92dZUIyVOtzxC0mdMS-xf/statement/)** 有一个由 $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`，在 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` 提交的序列输出到标准输出。 以下是一个样例的程序运行示例： | 调用 | 返回值 | 说明 | |-----------------------|--------|-------------------------------------------| | `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 \leq n=5$ 次询问，答案正确，得 $100\%$ 分数 | **附加样例** 1. 该样例满足 $n=1000, a=0^{500}1^{500}$（前 $500$ 个 $0$，后 $500$ 个 $1$）； 2. 该样例满足 $n=200000, a=(01)^{100000}$（$01$ 重复 $100000$ 次）。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $3 \leq n \leq 1000$ | $50$ | | $2$ | $3 \leq n \leq 200000$| $50$ | 设 $m$ 为你的程序在单个测试点中调用 `suma` 的最大次数，你的得分将按以下规则计算（若超过时间限制一半，则按比例缩减）： | 调用次数 | 得分百分比 | | :---: | :--: | | $m \leq n$ | 测试点的 $100\%$ 分数 | | $m = n+1$ | 测试点的 $80\%$ 分数 | | $m \leq n^{2}-n$ | 测试点的 $50\%$ 分数 | | $m > n^{2}-n$ | 测试点的 $0\%$ 分数（判为 `Wrong Answer`） |