問題一覧 > 通常問題

No.1959 Prefix MinMax

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 54
作問者 : 👑 tute7627tute7627 / テスター : 👑 PCTprobabilityPCTprobability
10 ProblemId : 7834 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-27 22:22:17

問題文

この問題はインタラクティブな問題です。

$(1,2,\dots,N)$ の順列 $P$ があります。

あなたは以下のようなクエリを $10$ 回まで行うことができます。

  • 長さ $N - 1$ の $0$ と $1$ からなる数列 $A$ を送り、以下のように定義される長さ $N$ の数列 $B$ を受け取る。
    • $B_1 = P_1$
    • $B_{i+1} = \min(B_i, P_{i+1})$ $(1 \le i \le N-1,A_i = 0$ の場合$)$
    • $B_{i+1} = \max(B_i, P_{i+1})$ $(1 \le i \le N-1,A_i = 1$ の場合$)$

$P$ を特定してください。

$T$ 個のテストケースが与えられます。

入出力

最初に、 テストケースの個数 $T$ が与えられます。 
$T$
各テストケースでは、まず順列 $P$ の長さ $N$ が与えられます。 
$N$
クエリを行う場合、以下のように長さ $N-1$ の $0$ と $1$ からなる数列 $A$ を空白区切りで出力する必要があります。 
$? \ A_1 \ A_2 \ \dots \ A_{N-1}$
返答として問題文で定義された長さ $N$ の数列 $B$ が与えられます。 
$B_1 \ B_2 \ \dots \ B_N$
$10$ 回以下のクエリの後、以下のように $(1,2,\dots,N)$ の順列 $P$ (22:21 訂正) を空白区切りで出力してください。 
$! \ P_1 \  P_2 \ \dots \ P_N$

注意
  • $A$ や $P$ の出力後は標準出力の flush を行ってください。
  • 出力に関する指示に従わなかった場合、flush を行わなかった場合のジャッジ結果は不定です。

制約

  • $1 \le T \le 10$
  • $2 \le N \le 1000$

サンプル

サンプル1

以下のようなやり取りが考えられます。

入力出力説明
2$2$ 個のテストケースが与えられます。
3$1$ 個目のテストケースでは、$N=3$ です。
? 0 0$A=(0,0)$ でクエリを行います。
2 1 1$B=(2,1,1)$ となりました。
? 0 1$A=(0,1)$ でクエリを行います
2 1 3$B=(2,1,3)$ となりました。
! 2 1 3$P=(2,1,3)$ と回答します。
2$2$ 個目のテストケースでは、$N=2$ です。
! 1 2クエリは $0$ 回でも構いません。

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