問題一覧 > 通常問題

No.2967 Nana's Plus Permutation Game

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

Story

Nana has learned addition and can now point to the result for us, so let's use this to play a permutation guessing game.

If the result is not in the permutation, she gets a little grumpy, but that can't be helped, so you don't need to worry about it.

However, she gets tired if you ask too many questions, so please keep them to a minimum.

Problem Statement

There is a permutation $P=(P_1,P_2,\cdots,P_{N})$ of $(1,2,\cdots,N)$ with $N$ elements. You are given $N$, but $P$ is not given and is kept hidden by the judge.

You can send the following query to the judge.

  • Choose integers $i,j$ between $1$ and $N$, inclusive. If $P_i+P_j \leq N$, you are given the integer $k$ such that $P_i+P_j=P_k$; otherwise, you are given $-1$.

  • You can use this query at most $2N$ times. Find $P$.

    Constraints

  • $2 \leq N \leq 5000$
  • $P$ is a permutation of $(1,2,\cdots,N)$
  • $P$ is fixed for each test case. $P$ does not change in response to queries.
  • All inputs are integers
  • Input and Output

    First, $N$ is given by the judge.

    $N$

    After that, you can send queries in the following format at most $2N$ times. They must satisfy $1 \leq i,j \leq N$.
    $1$ $i$ $j$

    The judge responds with the answer to the query. If $P_i+P_j \leq N$, you are given the integer $k$ such that $P_i+P_j=P_k$; otherwise, you are given $-1$.
    $k$

    When outputting the answer, print it in the following format. Terminate your program immediately after printing it.
    $2$ $P_1$ $P_2$ $\cdots$ $P_{N}$

    Notes

  • Print a trailing newline and flush the output after each output. Otherwise, the verdict may be TLE or WA.
  • The verdict for invalid output or behavior is undefined. Be careful not to print extra spaces, newlines, and so on.
  • After printing $P$, terminate your program immediately. If it does not terminate, the verdict is undefined.
  • Printing the answer does not count toward the number of queries.
  • Sample

    The following is one example.
    Program OutputJudge OutputExplanation
    4First, $N$ is given. Here, the judge is hiding $P=(1,4,2,3)$.
    1 1 3The query $i=1,j=3$ is sent to the judge.
    4 Since $P_1+P_3=3=P_4$, $4$ is given.
    1 1 4The query $i=1,j=4$ is sent to the judge.
    2 Since $P_1+P_4=4=P_2$, $2$ is given.
    1 4 4The query $i=4,j=4$ is sent to the judge.
    -1Since $P_4+P_4=6>4$, $-1$ is given.
    2 1 4 2 3The permutation $(1,4,2,3)$ is printed as the answer. It matches $P$, so this is correct.

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