| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 0 | 0 | 0 | 0.000% |
This is an interactive problem.
Vim, Emacs, and Nano are playing a guessing game. Vim secretly told Nano a random binary sequence $\{a_i\}$ of length $n$. Emacs can query Nano with a set of indices $I \subseteq \{1, 2, \ldots, n\}$. Nano will reply with $\sum_{i \in I} a_i$. Could you please help Emacs find $\{a_i\}$ in less than $n/2$ queries? Additionally, the total size of the sets in all queries must not be greater than 3ドルn$.
The first line of input contains an integer $n$.
You can use any of the following operations and write it to standard output:
? $k$ $i_1$ $i_2$ $\ldots$ $i_k$": Send a query with $I = \{i_1, i_2, \ldots, i_k\}$. The elements must be distinct. Nano will write the result back to standard input. There must be less than $n/2$ queries, and the sum of $k$ for all queries must not be greater than 3ドルn$.= $a_1 a_2 \ldots a_n$": Submit the binary sequence $\{a_i\}$ you found. Note that there are no spaces between $a_i$. Your program must exit gracefully after this operation.Remember to end the line and flush the standard output after each operation. For example, you can use the function fflush(stdout) in C or C++, System.out.flush() in Java, flush(output) in Pascal, or sys.stdout.flush() in Python.
4 2 1 2
? 4 1 2 3 4 ? 2 1 2 ? 2 2 3 = 0110
The size $n = 10^5$ in all tests. The example with $n = 4$ shows the format but will not be tested.
There are at most 50ドル$ tests in this problem. The tests were generated randomly, but are fixed in advance. In each test, every binary sequence of length $n$ had the probability of 1ドル/2^n$ to be generated.