Code Submission Evaluation System Login

KILO 2018 4/5

Start:2018-09-27 16:30:00
End:2018-09-27 18:30:00
 

Tasks | Scoreboard | Statistics


CSES - KILO 2018 4/5 - BarrelsCSES - Barrels

Barrels

Time limit:2.00 s
Memory limit:512 MB

This is an interactive problem.

Uolevi is inspecting a line of $n$ barrels, each containing some distinct amount of water. He wants to find the order of the barrels when sorted into ascending order by the amount of water they contain.

Normally this would be an easy task for a master barrel inspector like Uolevi, but these barrels are special! Somehow, Uolevi is unable to simply find out the amount of water in each barrel, so he has to use a special tool, called the center finder.

Given a set of barrels $B = \left\{b_{1}, \dots, b_{k}\right\}$ with some odd $k$, the center finder finds the index of the median of the given barrels.

More formally, it finds the unique index $j \in B$ such that $W(b_{i}) < W(j)$ holds for $\frac{k-1}{2}$ indices $i$, and $W(j) < W(b_{i})$ holds for $\frac{k-1}{2}$ indices $i$, where $W(j)$ is the amount of water in the $j$'th barrel.

For example, if $W = \left[10, 30, 20, 50, 40\right]$, and Uolevi gives the center finder $B = \left\{1, 2, 3\right\}$, it outputs $3$. If given $B = \left\{1, 2, 3, 4, 5\right\}$, it outputs $2$.

You can make two kinds of queries: After every query of the first type you make, the grader outputs a single integer $j \in B$: the index found by the center finder.

After every query of the second type, the grader outputs $1$ if the order given was the correct increasing order of the barrels, and $-1$ otherwise.

If the grader outputs $1$, you have found the order of the barrels and have succeeded. What your program does after this doesn't matter.

You can make at most $1000$ queries, including the final one.

Interaction

The first line of input contains a integer $n$: The amount of barrels.

To make a query of the first type, output $?$ $k$ $b_{1}$ $\dots$ $b_{k}$ in a single line, where $B = \left\{b_{1}, \dots, b_{k}\right\}$, and $k = \left|B\right|$ is odd.

After every query of the first type you make, the next line of input contains a single integer $j \in B$: the index returned by the center finder.

To make a query of the second type, output $!$ $b_{1}$ $\dots$ $b_{n}$, where $b_{1} \dots b_{n}$ is some permutation of the integers from $1$ to $n$.

After every query of the second type you make, the next line of input contains a single integer $v \in \left\{-1, 1\right\}$. If $v = 1$, the order was correct, and you have succeeded. Otherwise, the order wasn't increasing.

The grader is not adaptive.

Constraints
It is guaranteed that all barrels have distinct amounts of water.

Example

in: 3
out: ? 3 1 2 3
in: 3
out: ! 2 3 1
in: -1
out: ! 1 3 2
in: 1

Explanation:
In this example, the amounts of water are 10 30 20.

Example 2

in: 5
out: ? 3 1 2 3
in: 3
out: ? 3 2 3 4
in: 2
out: ? 3 3 4 5
in: 5
out: ? 3 2 3 5
in: 2
out: ! 1 5 2 3 4
in: -1
out: ! 1 3 2 5 4
in: 1

Explanation:
In this example, the amounts of water are 10 30 20 50 40.