시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 2048 MB0000.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 $3n$.

The first line of input contains an integer $n$.

You can use any of the following operations and write it to standard output:

  1. "? $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 $3n$.
  2. "= $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.

예제 입력 1

4
2
1
2

예제 출력 1

? 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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.