Secure Password
Contest: Codeforces Round 648 (Div. 2)
Difficulty rating: 2800
Tags: bitmasks, combinatorics, constructive algorithms, interactive, math

This is an interactive problem.

Ayush devised yet another scheme to set the password of his lock. The lock has $$$n$$$ slots where each slot can hold any non-negative integer. The password $$$P$$$ is a sequence of $$$n$$$ integers, $$$i$$$-th element of which goes into the $$$i$$$-th slot of the lock.

To set the password, Ayush comes up with an array $$$A$$$ of $$$n$$$ integers each in the range $$$[0, 2^{63}-1]$$$. He then sets the $$$i$$$-th element of $$$P$$$ as the bitwise OR of all integers in the array except $$$A_i$$$.

You need to guess the password. To make a query, you can choose a non-empty subset of indices of the array and ask the bitwise OR all elements of the array with index in this subset. You can ask no more than 13 queries.

Input format:
The first line of input contains one integer $$$n$$$ $$$(2 \le n \le 1000)$$$ — the number of slots in the lock.

Interaction format:
To ask a query print a single line:

- In the beginning print "? c " (without quotes) where $$$c$$$ $$$(1 \leq c \leq n)$$$ denotes the size of the subset of indices being queried, followed by $$$c$$$ distinct space-separated integers in the range $$$[1, n]$$$.

For each query, you will receive an integer $$$x$$$ — the bitwise OR of values in the array among all the indices queried. If the subset of indices queried is invalid or you exceeded the number of queries then you will get $$$x = -1$$$. In this case, you should terminate the program immediately.

When you have guessed the password, print a single line "! " (without quotes), followed by $$$n$$$ space-separated integers  — the password sequence.

Guessing the password does not count towards the number of queries asked.

The interactor is not adaptive. The array $$$A$$$ does not change with queries.

After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.

Hacks

To hack the solution, use the following test format:

On the first line print a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$ — the number of slots in the lock. The next line should contain $$$n$$$ space-separated integers in the range $$$[0, 2^{63} - 1]$$$ — the array $$$A$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The array $$$A$$$ in the example is $$$\{{1, 2, 4\}}$$$. The first element of the password is bitwise OR of $$$A_2$$$ and $$$A_3$$$, the second element is bitwise OR of $$$A_1$$$ and $$$A_3$$$ and the third element is bitwise OR of $$$A_1$$$ and $$$A_2$$$. Hence the password sequence is $$$\{{6, 5, 3\}}$$$.

Example input:
3

1

2

4

Example output:
? 1 1

? 1 2

? 1 3

! 6 5 3

Editorial:
Key Idea:
Unlike the last version of the problem, this is not doable using a binary search.
Solution using more queries:
It is possible to solve the problem using $$$2\cdot \log{n}$$$ queries in the following way:
For each $$$i$$$, we ask the bitwise OR of all numbers at indices which have the $$$i$$$-th bit set in their binary representation. We also ask the bitwise OR of all numbers at indices which do not have the $$$i$$$-th bit set in their binary representation.
Suppose we want to calculate the bitwise OR of all numbers except the $$$i$$$-th number. Let the bitwise OR be equal to $$$a$$$ (initialize $$$a= 0$$$). We iterate on all indices $$$j$$$ from $$$1$$$ to $$$n$$$ (except $$$i$$$). If $$$j$$$ is a submask of $$$i$$$, that is $$$j \wedge i = j$$$ (where $$$\wedge$$$ is the bitwise AND operator), then there must be some bit $$$k$$$ that is set in $$$i$$$ but not in $$$j$$$ (since $$$i \ne j$$$). In this case we replace $$$a$$$ by $$$a \vee x$$$ where $$$\vee$$$ is the bitwise OR operator and $$$x$$$ is the bitwise OR of numbers at indices that do no have the $$$k$$$-th bit set. Similarly, if $$$j$$$ is not a submask of $$$i$$$ then there must be some bit $$$k$$$ which is set in $$$j$$$ but not in $$$i$$$. In that case we use the bitwise OR of numbers at indices that have the $$$k$$$-th bit set.
In doing so, we included the contribution of each element except $$$i$$$ at least once. Note that this works because taking the bitwise OR with the same number more than once does not affect the answer.
For example, if $$$n=4$$$ and indices are number $$$0$$$ to $$$3$$$, then we need to ask $$$4$$$ queries: $$$\{{0, 2\}}$$$ (bit $$$0$$$ not set), $$$\{{1, 3\}}$$$ (bit $$$0$$$ set), $$$\{{0, 1\}}$$$ (bit $$$1$$$ not set), $$$\{{2, 3\}}$$$ (bit $$$1$$$ set).
Solution:
Note that in the suboptimal solution, we assigned a bitmask to each index (in that case bitmask for index $$$i$$$ was equal to $$$i$$$). What if we assign these masks in a different way?
Suppose we are able to assign the masks in such a way that no two masks assigned to two indices are submasks of each other. In this case, we do not need to ask bitwise OR of indices which do not have the $$$i$$$-th bit set since for each pair of indices, there is a bit which is set in one but not in the other.
For example, if $$$n = 4$$$, we can assign masks 1100, 1010, 1001 and 0110 (in binary representation). Now for each bit $$$i$$$, we will only query the indices which have the $$$i$$$-th bit set. In this case, for bit $$$0$$$ we ask $$$\{{3\}}$$$, for bit $$$1$$$ we ask $$$\{{2, 4\}}$$$, for bit $$$2$$$ we ask $$$\{{1, 4\}}$$$ and for bit $$$3$$$ we ask $$$\{{1, 2, 3\}}$$$. Let $$$x_0, x_1, x_2, x_3$$$ be bitwise OR of these four subsets respectively. Then the elements of the password are $$$x_0 \vee x_1$$$, $$$x_0 \vee x_2$$$, $$$x_1 \vee x_2$$$ and $$$x_0 \vee x_3$$$ respectively.
What is the minimum number of bits we need to assign masks in such a way?
We are given the bound of $$$13$$$ queries. There are $$$1716$$$ numbers upto $$$2^{13}$$$ which have $$$6$$$ bits set in their binary representation. Clearly no two of these numbers would be submaks of each other. So we can use them to assign the masks!
It can be shown using Sperner's theorem that we need at least $$$13$$$ queries to assign submaks in the above manner.
Time complexity: $$$O(2^q + n \cdot q)$$$ where $$$q$$$ is the number of queries asked.