No.3592 I Love LIS
Problem Statement
This is an interactive problem (your program and the judge system communicate through standard input and output).
In an ancient temple there is an "Oracle", which keeps hidden a permutation $P = (P_1, P_2, \dots, P_N)$ of length $N$. A permutation is a sequence in which each integer from $1$ to $N$ appears exactly $1$ time.
You are trying to identify this hidden permutation by sending questions (queries) to the Oracle. In $1$ query, you specify any integer array $A = (A_1, A_2, \dots, A_N)$ of length $N$. The Oracle immediately rearranges the array according to the permutation $P$ and generates a new sequence $S$. Specifically, $S_i = A_{P_i} \ (1 \le i \le N)$. The Oracle then returns the length of the longest strictly increasing subsequence (LIS) of the generated sequence $S$.
* A strictly increasing subsequence is a sequence $S_{i_1}, S_{i_2}, \dots, S_{i_k} \ (i_1 < i_2 < \dots < i_k)$ obtained by extracting some elements from $S$ and arranging them in their original order, such that $S_{i_1} < S_{i_2} < \dots < S_{i_k}$.
Identify the entire hidden permutation $P$ using as few queries as possible.
Input and Output
First, the length $N$ of the permutation is given from standard input.
$N$
Then, your program may send queries to the Oracle. Print each query to standard output in the following format.
? $A_1\ A_2 \cdots A_N$
Here, each $A_i$ must be an integer satisfying $-10^9 \le A_i \le 10^9$.
After you send a query, the judge system gives the LIS length $X$ to standard input.
$X$
- When $X \ge 0$: $X$ is the length of the LIS of the generated sequence $S$.
- When $X = -1$: This is given if the format of the query you sent was invalid or if the query limit was exceeded. In this case, terminate your program immediately. Otherwise, the judge result is undefined (it may be
TLEor similar).
Once you have identified all elements of the permutation, print your answer in the following format and terminate your program normally. Printing the answer does not count toward the number of queries.
! $P_1\ P_2 \cdots P_N$
[Note]
Be sure to flush standard output after each output (both queries and the answer). If you do not flush, you may get TLE or WA.
Print a newline at the end.
Constraints
- $2 \le N \le 1000$
- $N$ is an integer
- The maximum number of queries you may send is $12,000$
Sample
Sample 1
Input
3 2 1
Output
? 10 20 30 ? 0 0 0 ! 3 1 2
This sample shows an example of the interaction when $N=3$ and the hidden permutation is $P = (3, 1, 2)$. (* During actual execution, the input and output take place interactively.)
- First, the length $N=3$ is given to standard input.
- Your program sends
? 10 20 30as the first query. The array is then $A_1=10, A_2=20, A_3=30$. The Oracle internally generates $S = (A_{P_1}, A_{P_2}, A_{P_3}) = (A_3, A_1, A_2) = (30, 10, 20)$. The LIS of $S$ is $(10, 20)$, and its length is $2$, so the Oracle returns2to standard input. - Your program sends
? 0 0 0as the next query. The Oracle internally generates $S = (0, 0, 0)$. Since the subsequence must be strictly increasing, the LIS length is $1$, and the Oracle returns1to standard input. - Since the permutation has been identified as $P = (3, 1, 2)$ from this and other information, your program prints
! 3 1 2and terminates. The number of queries sent before the answer phase is $2$, which does not exceed the limit, so this is judged correct.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。