問題一覧 > 通常問題

No.1959 Prefix MinMax

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 53
作問者 : 👑 tute7627 / テスター : PCTprobability
お気に入りにしたユーザー ProblemId : 7834 / 自分の提出
問題文最終更新日: 2022-05-27 22:22:17
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.

InputOutputExplanation
2$2$ test cases are given.
3In the $1$st test case, $N=3$.
? 0 0Make a query with $A=(0,0)$.
2 1 1The result is $B=(2,1,1)$.
? 0 1Make a query with $A=(0,1)$.
2 1 3The result is $B=(2,1,3)$.
! 2 1 3Answer $P=(2,1,3)$.
2In the $2$nd test case, $N=2$.
! 1 2It is fine to make $0$ queries.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。