問題一覧 > 通常問題

No.2967 Nana's Plus Permutation Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 17
作問者 : ねしん / テスター : 遭難者
2 ProblemId : 11519 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-05 11:14:56

ストーリー

ナナが足し算を習い、結果を指し示してくれるようになったので、これで順列当てゲームを行いましょう。

順列の中にないと、少し不機嫌になりますがそこはしょうがないので気にしなくていいです。

ただし、質問回数が多いと疲れてしまうので、最小限にしてください。

問題文

要素数が NN 個の (1,2,⋯ ,N)(1,2,\cdots,N) の順列 P=(P1,P2,⋯ ,PN)P=(P_1,P_2,\cdots,P_{N}) があります。NN は与えられますが、PP は与えられずジャッジが隠し持っています。

あなたはジャッジに対して以下のクエリを送ることが出来ます。

  • 11 以上 NN 以下の整数 i,ji,j を選ぶ。Pi+Pj≤NP_i+P_j \leq N なら Pi+Pj=PkP_i+P_j=P_k となる整数 kk が、そうでなければ、−1-1 が与えられる。

    • このクエリは 2N2N 回まで使用することが出来ます。PP を求めてください。

    制約

  • 2≤N≤50002 \leq N \leq 5000
  • PP は (1,2,⋯ ,N)(1,2,\cdots,N) の順列
  • PP は各テストケースごとに固定である。質問クエリによって PP が変動することはない。
  • 入力はすべて整数

    • 入出力

    まず NN がジャッジ側から渡されます。 

    NN

    そのあと、あなたは 2N2N 回まで以下の形でクエリを送ることが出来ます。1≤i,j≤N1 \leq i,j \leq N を満たす必要があります。 
    11 ii jj

    ジャッジ側の返答としてクエリに対する答えが与えられます。Pi+Pj≤NP_i+P_j \leq N なら Pi+Pj=PkP_i+P_j=P_k となる整数 kk が、そうでなければ、−1-1 が与えられます。 
    kk

    答えを出力するときは以下の様に出力してください。出力した後は直ちにプログラムを終了してください。 
    22 P1P_1 P2P_2 ⋯\cdots PNP_{N}

    注意点

  • 各出力のたびに末尾改行と出力の flush をしてください。そうしなかった場合、ジャッジ結果がTLEやWAになる可能性があります。
  • 不正な出力や動作に対するジャッジは不定です。余分な空白や改行などを出力しないよう注意してください。
  • PP を出力した場合、すぐにプログラムを修正してください。終了しなければジャッジ結果は不定です。
  • 解答の出力はクエリ回数に含まれません。

    • サンプル

    以下は一例です。
    プログラム側の出力ジャッジ側の出力説明
    4まず、始めに NN が渡されます。このとき、ジャッジ側では P=(1,4,2,3)P=(1,4,2,3) を隠し持っています。
    1 1 3クエリとして i=1,j=3i=1,j=3 をジャッジ側に送りました。
    4 P1+P3=3=P4P_1+P_3=3=P_4 なので 44 が与えられます。
    1 1 4クエリとして i=1,j=4i=1,j=4 をジャッジ側に送りました。
    2 P1+P4=4=P2P_1+P_4=4=P_2 なので 22 が与えられます。
    1 4 4クエリとして i=4,j=4i=4,j=4 をジャッジ側に送りました。
    -1P4+P4=6>4P_4+P_4=6>4 なので −1-1 が与えられます。
    2 1 4 2 3答えとして順列 (1,4,2,3)(1,4,2,3) を出力しました。これは PP と一致するので正解となります。

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