No.2577 Simple Permutation Guess
Problem Statement
The judge has a permutation $P$ of length $n$. Given only $n$, guess the permutation $P$ using the following query at most $\lfloor \lfloor (n - 1) \log_2 n \rfloor - \frac{n - 1}{2} +1 \rfloor$ times.
Query: send a permutation $Q$. You obtain whether $Q \le P$ holds.
Here, a permutation of length $n$ is a rearrangement of $1, 2, \dots, n$. Also, $Q \le P$ means that either $Q_i=P_i$ for all $1 \le i \le n$, or there exists some $j$ such that $Q_i=P_i$ for all $1 \le i < j$ and $Q_j < P_j$.
About the Judge
The judge of this problem is adaptive. The judge may change $P$ as long as it does not contradict its responses to the queries.
Addendum: Fixed a typo (corrected "ジャッジについてについて" to "ジャッジについて") (0:12)
About the Evil Cases
In this problem, the constraints are kept small because of the speed of the reactive judge, but evil cases (see "正解判定のポリシー" (Policy on Judging Correct Answers) here) are included to distinguish fast solutions. The results of these cases do not affect the judge result.
Constraints
- $1 \le n \le 250$
- $P$ is a permutation.
- All inputs are integers.
Constraints of the Evil Cases
- $250 < n \le 400$
- $P$ is a permutation.
- All inputs are integers.
Input and Output
First, an integer $n$ is given.
$n$
Next, you may send queries in the following format at most $\lfloor \lfloor (n - 1) \log_2 n \rfloor - \frac{n - 1}{2} +1 \rfloor$ times. Here, the sequence $Q$ must be a permutation.
$?\ Q_1\ Q_2\ \dots\ Q_n$
You are given $ret=1$ if $Q \le P$, $ret=0$ if $Q>P$, and $ret=-1$ if there was some problem with the judge.
$ret$
Here, if $ret = -1$, terminate your program immediately. Otherwise, either continue querying or answer with a permutation.
To answer with a permutation, output it in the following format. This output is not counted as a query.
$!\ Q_1\ Q_2\ \dots\ Q_n$
After that, terminate your program immediately.
Notes
- After each output, print a trailing newline and flush the output.
- The judge's behavior for invalid output or actions may be undefined.
Sample
This is one example of an interaction and may not be an optimal way of sending queries.| Input | Output | Explanation |
|---|---|---|
5 | $n=5$ | |
? 1 2 3 4 5 | Sent a query with $Q=1, 2, 3, 4, 5$. | |
1 | The response to the query was $Q \le P$. | |
? 5 4 3 2 1 | Sent a query with $Q=5, 4, 3, 2, 1$. | |
0 | The response to the query was $Q>P$. | |
? 2 5 1 4 3 | Sent a query with $Q=2, 5, 1, 4, 3$. | |
1 | The response to the query was $Q \le P$. | |
? 2 5 4 3 1 | Sent a query with $Q=2, 5, 4, 3, 1$. | |
1 | The response to the query was $Q \le P$. | |
! 2 5 4 3 1 | Sent an answer with $Q=2, 5, 4, 3, 1$. | |
The judge result is WA. It was $P=2,5,4,3,1$, but since, for example, $P=5,4,3,1,2$ also does not contradict the queries so far, the judge changed $P$. |
AC.
| Input | Output | Explanation |
|---|---|---|
? 3 1 2 4 5 | Sent a query with $Q=3, 1, 2, 4, 5$. | |
0 | The response to the query was $Q > P$. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
null