No.2496 LCM between Permutations
タグ : / 解いたユーザー数 52
作問者 :
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)$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。