No.1959 Prefix MinMax
レベル :
/ AI推定難易度 : 1500
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : / 解いたユーザー数 53
作問者 : 👑
tute7627
/ テスター :
PCTprobability
タグ : / 解いたユーザー数 53
作問者 : 👑
tute7627
/ テスター :
PCTprobability
問題文最終更新日: 2022-05-27 22:22:17
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 345
(順位表)
の他の問題:
Problem Statement
This is an interactive problem.
There is a permutation $P$ of $(1,2,\dots,N)$.
You can make the following query up to $10$ times.
-
Send a sequence $A$ of length $N - 1$ consisting of $0$ and $1$, and receive a sequence $B$ of length $N$ defined as follows.
- $B_1 = P_1$
- $B_{i+1} = \min(B_i, P_{i+1})$ $(1 \le i \le N-1,A_i = 0$ case$)$
- $B_{i+1} = \max(B_i, P_{i+1})$ $(1 \le i \le N-1,A_i = 1$ case$)$
Determine $P$.
You are given $T$ test cases.
Input and Output
First, the number of test cases $T$ is given.$T$For each test case, the length $N$ of the permutation $P$ is given first.
$N$To make a query, you must output a sequence $A$ of length $N-1$ consisting of $0$ and $1$, separated by spaces, as follows.
$? \ A_1 \ A_2 \ \dots \ A_{N-1}$
In response, the sequence $B$ of length $N$ defined in the problem statement is given.
$B_1 \ B_2 \ \dots \ B_N$After at most $10$ queries, output the permutation $P$ of $(1,2,\dots,N)$ (corrected at 22:21), separated by spaces, as follows.
$! \ P_1 \ P_2 \ \dots \ P_N$
Notes
- Flush standard output after outputting $A$ or $P$.
- If you do not follow the output instructions or do not flush, the judge result is undefined.
Constraints
- $1 \le T \le 10$
- $2 \le N \le 1000$
Sample
Sample 1
The following interaction is possible.
| Input | Output | Explanation |
|---|---|---|
2 | $2$ test cases are given. | |
3 | In the $1$st test case, $N=3$. | |
? 0 0 | Make a query with $A=(0,0)$. | |
2 1 1 | The result is $B=(2,1,1)$. | |
? 0 1 | Make a query with $A=(0,1)$. | |
2 1 3 | The result is $B=(2,1,3)$. | |
! 2 1 3 | Answer $P=(2,1,3)$. | |
2 | In the $2$nd test case, $N=2$. | |
! 1 2 | It is fine to make $0$ queries. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。