There is a sequence $a_0, \dots, a_{n-1}$ consisting of $0$s and $1$s. You do not know this sequence, but you can ask for the sum of any pair of distinct elements of the sequence. Your task is to guess the sequence using a small number of such queries.
Communication
Implement a program that guesses the sequence of zeros and ones using the provided library that answers the queries. To use the library, include the following in your program:
- C/C++:
#include "zerlib.h" - Python:
from zerlib import daj_n, suma, odpowiedz
The library provides the following functions:
daj_n()– This function returns an integer $n$, representing the length of the unknown sequence of zeros and ones.suma(i, j)– This function returns the result $a_i + a_j$, provided $0 \le i, j < n$ and $i \neq j$. Otherwise, calling it results in an incorrect answer.odpowiedz(a)– This function allows you to submit the resulting sequence. It must be called exactly once. It takes an array $a[0..n-1]$ (given as astd::vector<int>in C++ or a list in Python) representing the resulting sequence $a[0], \dots, a[n-1]$. After this function is executed, the program will be automatically terminated. If the sequence provided in the function is incorrect or its length is different from $n$, it will result in an incorrect answer.
The library does not have to generate the sequence $a_0, \dots, a_{n-1}$ at the beginning of the interaction with your program. It may change the elements of the sequence during the interaction, as long as the new elements are still consistent with the results returned by previous calls to the suma function.
Your program must not open any files or use standard input and output. It may use standard diagnostic output (stderr), but keep in mind that this consumes valuable time.
Your solution will be compiled with the library using the following commands:
- C/C++:
g++ -O3 -static -std=c++17 zerlib.cpp zer.cpp - Python:
python3 zer.py
Note: The memory limit mentioned above applies only to your solution and therefore does not include the memory used by the library.
Subtasks
The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.
| Subtask | Constraints | Points |
|---|---|---|
| 1 | $3 \le n \le 1000$ | 50 |
| 2 | $3 \le n \le 200\,000$ | 50 |
If $m$ is the maximum number of calls to the suma function that your program performed in a single test case, your solution will receive the following percentage of points for the test (scaled accordingly if half the time limit is exceeded):
| Number of calls | Percentage of points |
|---|---|
| $m \le n$ | 100% of points for the test |
| $m = n + 1$ | 80% of points for the test |
| $m \le n^2 - n$ | 50% of points for the test |
| $m > n^2 - n$ | 0% of points for the test (Wrong Answer verdict) |
Examples
Example 1
| Call | Result | Description |
|---|---|---|
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$, so $a_3 = a_4 = 1$ |
suma(0, 3) |
$2$ | $a_0 + a_3 = 2$, so $a_0 = 1$, which also implies $a_1 = 0$ and $a_2 = 1$ |
odpowiedz({1,0,1,1,1}) |
– | Correct answer using $m = 4 \le n = 5$ queries, 100% of points for the test |
"Evaluation" tests: 1. $n = 1000, a = 0^{500}1^{500}$ 2. $n = 200\,000, a = (01)^{100\,000}$
Note
Sample incorrect solutions along with sample libraries can be found in the dlazaw folder. The libraries may differ in behavior from those used for the final evaluation of solutions and may not meet the requirements of the task. They are only intended to show how to interact with the program.
Your solution compiled with the sample library reads the description of the sequence from standard input – the number $n$, and then the subsequent numbers $a_0, \dots, a_{n-1}$, separated by spaces – then uses them to answer suma queries from your program, and finally prints the sequence passed in the odpowiedz function call to standard output.