問題一覧 > 通常問題

No.2124 Guess the Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 132
作問者 : 遭難者遭難者 / テスター : 👑 potato167potato167 とりゐとりゐ
4 ProblemId : 8727 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-17 09:23:12

問題文

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

sounansya 君は $1$ 以上 $N$ 以下の正整数を並び替えてできる長さ $N$ の順列 $P=(P_1,\ldots,P_N)$ を持っています。
あなたは以下の質問を $N-1$ 回まで行うことができます :
  • $1\le l< r\le N$ を満たす整数の組 $(l,r)$ を選ぶ。そして、 $\displaystyle \sum_{i=l}^r P_i$ の値を聞く。
    • sounansya 君が持っている順列を当ててください。

    制約

  • 入力は全て整数
  • $3\le N\le 1000$

    • 入出力

    この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
    最初に、順列の長さ $N$ を標準入力から受け取ってください。 
    $N$

    次に、順列を当てることができるまで質問を繰り返してください。
    質問は、以下の形式で標準出力に出力してください。 

    $?$ $l$ $r$
    これに対する応答は、次の形式で標準入力から与えられます。 
    $S$
    ここで、 $S$ は質問に対する答えです。
    順列が分かったら、以下の形式で標準出力に出力してください。 
    $!$ $P_1$ $\ldots$ $P_N$

    注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った場合のジャッジ結果は不定です。
  • 順列を解答した後はすぐにプログラムを終了させてください。終了しなければジャッジの結果は不定です。
  • 解答をするクエリは質問回数に含まれません。

    • サンプル

    以下は $N=3$ 、 $P=(3,1,2)$ として対話が始まった場合の対話の一例です。
    入力 出力 説明
    3 まず $N$ が入力として与えられます。
    ? 2 3 $P_2+P_3$ の値を聞きます。
    3 $P_2+P_3=3$ なので、 $3$ が返されます。
    ? 1 2 $P_1+P_2$ の値を聞きます。
    4 $P_1+P_2=4$ なので、 $4$ が返されます。
    ! 3 1 2 答えは $P=(3,1,2)$ だと分かったので、これを出力します。

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