問題一覧 > 通常問題

No.2496 LCM between Permutations

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

Problem Statement

This is an interactive problem.

You are given a positive integer $N$. In addition, permutations $A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N)$ of $(1,2,\dots,N)$ are hidden. You may ask the following question up to $3N$ times.

  • Question: Choose integers $i,j$ between $1$ and $N$, inclusive, and ask for the value of $\mathrm{lcm}(A_i,B_j)$.
Determine $A,B$. Note that $A,B$ are fixed throughout a test case, and $A,B$ do not change depending on the content of your questions.

Constraints

  • $1\leq N\leq 1000$
  • The permutations $A,B$ are fixed for each test case.
  • All inputs are integers.

Input and Output

First, the length $N$ of the permutations is given from standard input.

$N$

Next, repeat questions until you can determine $A,B$. Print each question to standard output in the following format.

? $i$ $j$

The answer to the question is given from standard input in the following format.

$X$

Here, $X=\mathrm{lcm}(A_i,B_j)$.

Once you have determined $A,B$, print them to standard output in the following format (print them on a single line). Then, terminate your program immediately.

! $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$

Notes

  • After each output, print a newline at the end and flush standard output. Otherwise, you may get TLE.
  • If you ask more than $3N$ questions or produce invalid output, the judge result is undefined.
  • Terminate your program immediately after printing your answer. Otherwise, the judge result is undefined.

Sample

This is an example of input and output for the case $N=3,A=(1,2,3),B=(3,1,2)$.
Input Output Explanation
3 First, $N$ is given.
? 1 2 Ask a question with $i=1,j=2$.
1 $\mathrm{lcm}(A_1,B_2)=1$.
? 3 2 Ask a question with $i=3,j=2$.
3 $\mathrm{lcm}(A_3,B_2)=3$.
? 3 3 Ask a question with $i=3,j=3$.
6 $\mathrm{lcm}(A_3,B_3)=6$.
! 1 2 3 3 1 2 We have determined that $A=(1,2,3),B=(3,1,2)$, so we output it as the answer.

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