No.2967 Nana's Plus Permutation Game
レベル :
/ AI推定難易度 : 1500
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : / 解いたユーザー数 19
作問者 :
twitteryou
/ テスター :
👑
qand
タグ : / 解いたユーザー数 19
作問者 :
問題文最終更新日: 2024-11-05 11:14:56
English (AI translation)
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.
You can use this query at most $2N$ times. Find $P$.
Constraints
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
Sample
The following is one example.| Program Output | Judge Output | Explanation |
|---|---|---|
4 | First, $N$ is given. Here, the judge is hiding $P=(1,4,2,3)$. | |
1 1 3 | The query $i=1,j=3$ is sent to the judge. | |
4 | Since $P_1+P_3=3=P_4$, $4$ is given. | |
1 1 4 | The query $i=1,j=4$ is sent to the judge. | |
2 | Since $P_1+P_4=4=P_2$, $2$ is given. | |
1 4 4 | The query $i=4,j=4$ is sent to the judge. | |
-1 | Since $P_4+P_4=6>4$, $-1$ is given. | |
2 1 4 2 3 | The permutation $(1,4,2,3)$ is printed as the answer. It matches $P$, so this is correct. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。