Guessing the Permutation via Median - Repovive Premier Round 2 | Repovive

This is an interactive problem. After each printed line, flush the output.

You are given an integer $n$ and an unknown permutation $p$ of $\{1,2,\dots,n\}$ . You must determine the entire permutation by asking at most $\left\lfloor \frac{5n}{4} \right\rfloor$ queries.

In one query, you choose an odd integer $k$ and then give $k$ distinct indices $i_1,i_2,\dots,i_k$ in the order you want. The given indices are not necessarily sorted.

The judge answers with two values:

Median index $m$ :
Consider the set $\{p_{i_1},p_{i_2},\dots,p_{i_k}\}$ . Since $k$ is odd, the median value is the $\frac{k+1}{2}$ -th smallest value. You receive an index $m \in \{i_1,i_2,\dots,i_k\}$ such that $p_m$ equals this median value.
Inversion parity $s$ :
Consider the sequence $(p_{i_1}, p_{i_2}, \dots, p_{i_k})$ in the same order as the indices you provided. Let $inv$ be the number of inversions in this sequence, meaning the number of pairs $(x,y)$ with $1 \le x < y \le k$ and $p_{i_x} > p_{i_y}$ . The judge returns $s = inv \bmod 2$ .

Constraints

$1 \le t \le 50$
$3 \le n \le 100$

Under these constraints, it is guaranteed that there exists a strategy that finds the permutation within the query limit.

The whole interaction is repeated for $t$ test cases.

t \\[0.5em] \left. \begin{array}{l} n \end{array} \right\} \times t

To ask a query, print:

? \ k \ i_1 \ i_2 \ \dots \ i_k

where $k$ is an odd integer between $1$ and $n$ , all $i_t$ are distinct, and $1 \le i_t \le n$ , then flush.

The judge replies with:

m \ s

as defined in the statement.

When you have determined the permutation, print:

! \ p_1 \ p_2 \ \dots \ p_n

Then flush.

You must use at most $\left\lfloor \frac{5n}{4} \right\rfloor$ queries.

Interactor Verdicts

You will get a $Wrong$ $Answer$ For the following cases:

$1-$ Your solution does not give a correct output (obviously)

$2-$ Your solution asks more queries than the problem specifies (Query Limit Exceeded)

$3-$ Your solution remains Idle without printing any queries (Idleness Limit Exceeded)

Keep in mind that not flushing the output may lead to unexpected verdicts.

This is an interactive problem. After each printed line, flush the output.

You are given an integer $n$ and an unknown permutation $p$ of $\{1,2,\dots,n\}$ . You must determine the entire permutation by asking at most $\left\lfloor \frac{5n}{4} \right\rfloor$ queries.

In one query, you choose an odd integer $k$ and then give $k$ distinct indices $i_1,i_2,\dots,i_k$ in the order you want. The given indices are not necessarily sorted.

The judge answers with two values:

Median index $m$ :
Consider the set $\{p_{i_1},p_{i_2},\dots,p_{i_k}\}$ . Since $k$ is odd, the median value is the $\frac{k+1}{2}$ -th smallest value. You receive an index $m \in \{i_1,i_2,\dots,i_k\}$ such that $p_m$ equals this median value.
Inversion parity $s$ :
Consider the sequence $(p_{i_1}, p_{i_2}, \dots, p_{i_k})$ in the same order as the indices you provided. Let $inv$ be the number of inversions in this sequence, meaning the number of pairs $(x,y)$ with $1 \le x < y \le k$ and $p_{i_x} > p_{i_y}$ . The judge returns $s = inv \bmod 2$ .

Constraints

$1 \le t \le 50$
$3 \le n \le 100$

Under these constraints, it is guaranteed that there exists a strategy that finds the permutation within the query limit.

The whole interaction is repeated for $t$ test cases.

t \\[0.5em] \left. \begin{array}{l} n \end{array} \right\} \times t

To ask a query, print:

? \ k \ i_1 \ i_2 \ \dots \ i_k

where $k$ is an odd integer between $1$ and $n$ , all $i_t$ are distinct, and $1 \le i_t \le n$ , then flush.

The judge replies with:

m \ s

as defined in the statement.

When you have determined the permutation, print:

! \ p_1 \ p_2 \ \dots \ p_n

Then flush.

You must use at most $\left\lfloor \frac{5n}{4} \right\rfloor$ queries.

Interactor Verdicts

You will get a $Wrong$ $Answer$ For the following cases:

$1-$ Your solution does not give a correct output (obviously)

$2-$ Your solution asks more queries than the problem specifies (Query Limit Exceeded)

$3-$ Your solution remains Idle without printing any queries (Idleness Limit Exceeded)

7F. Guessing the Permutation via Median

Constraints

Input

Interaction Protocol

Interactor Verdicts

Keep in mind that not flushing the output may lead to unexpected verdicts.

Constraints

Interactor Verdicts

Keep in mind that not flushing the output may lead to unexpected verdicts.