English · Original
Chinese · Translation
Formal · Original
_This is an interactive problem._
There is a *hidden* permutation $P$ of length $n$ and you have to find it. For this, you have to choose *two different* integers $i$ and $j$, and the jury will give you $"lcm"(P_i, P_j)$.
You can make no more than $2 n + 100$ queries in order to guess $P$.
A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[ 3, 1, 2, 5, 4 ]$ is a permutation, but $[ 1, 2, 1 ]$ is not a permutation (1 appears twice in the array) and $[ 2, 1, 4 ]$ is also not a permutation ($n = 3$, but $4$ is in the array).
One integer $3 <= n <= 10^5 :$ The size of the *hidden* permutation $P$. Then, the interaction will start.
After reading the length of the permutation $n,$ the interaction protocol is as follows :
After printing a query or the answer, do not forget to output at the end of the line and flush the output. Otherwise, you will get *Idleness limit exceeded*. To do this, use:
## Input
One integer $3 <= n <= 10^5 :$ The size of the *hidden* permutation $P$. Then, the interaction will start.
## Interaction
After reading the length of the permutation $n,$ the interaction protocol is as follows : To get $upright(l c m) (P_i, P_j)$, output the query in the format $? " "mathtt(i) " "mathtt(j)$ where $1 <= i eq.not j <= n.$ You can make at most $2 n + 100$ queries. When you find $P$, output $P$ in the format $! " "mathtt(P)_1 " "mathtt(P)_2 " "\\dots " "mathtt(P)_n$. Printing the permutation is not counted as one of $2 n + 100$ operations. In the first occurrence of a query *not conforming* to the given format, you will receive $-1$, and you should exit immediately to get a Presentation error verdict.
[samples]
## Note
After printing a query or the answer, do not forget to output at the end of the line and flush the output. Otherwise, you will get *Idleness limit exceeded*. To do this, use: *fflush(stdout)* or *cout.flush()* in C++ *fflush(stdout)* in C *System.out.flush()* in Java *stdout.flush()* in Python
[{"iden":"statement","content":"_This is an interactive problem._\n\nThere is a *hidden* permutation $P$ of length $n$ and you have to find it. For this, you have to choose *two different* integers $i$ and $j$, and the jury will give you $\"lcm\"(P_i, P_j)$.\n\nYou can make no more than $2 n + 100$ queries in order to guess $P$.\n\nA permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[ 3, 1, 2, 5, 4 ]$ is a permutation, but $[ 1, 2, 1 ]$ is not a permutation (1 appears twice in the array) and $[ 2, 1, 4 ]$ is also not a permutation ($n = 3$, but $4$ is in the array)."},{"iden":"input","content":"One integer $3 lt.eq n lt.eq 10^5 :$ The size of the *hidden* permutation $P$. Then, the interaction will start."},{"iden":"interaction","content":"After reading the length of the permutation $n,$ the interaction protocol is as follows : To get $upright(l c m) (P_i, P_j)$, output the query in the format $? \" \"mathtt(i) \" \"mathtt(j)$ where $1 lt.eq i eq.not j lt.eq n.$ You can make at most $2 n + 100$ queries. When you find $P$, output $P$ in the format $! \" \"mathtt(P)_1 \" \"mathtt(P)_2 \" \"dots.h \" \"mathtt(P)_n$. Printing the permutation is not counted as one of $2 n + 100$ operations. In the first occurrence of a query *not conforming* to the given format, you will receive $-1$, and you should exit immediately to get a Presentation error verdict. "},{"iden":"note","content":"After printing a query or the answer, do not forget to output at the end of the line and flush the output. Otherwise, you will get *Idleness limit exceeded*. To do this, use: *fflush(stdout)* or *cout.flush()* in C++ *fflush(stdout)* in C *System.out.flush()* in Java *stdout.flush()* in Python "}]}
**Definitions**
Let $ n \in \mathbb{Z} $ be the length of the hidden permutation $ P = (P_1, P_2, \dots, P_n) $, where $ P $ is a bijection from $ \{1, 2, \dots, n\} $ to $ \{1, 2, \dots, n\} $.
**Constraints**
1. $ 3 \leq n \leq 10^5 $
2. You may query at most $ 2n + 100 $ times.
3. Each query consists of two distinct indices $ i, j \in \{1, 2, \dots, n\} $, and returns $ \mathrm{lcm}(P_i, P_j) $.
**Objective**
Reconstruct the permutation $ P $ using at most $ 2n + 100 $ queries of the form $ \mathrm{lcm}(P_i, P_j) $.
API Response (JSON)
{
"problem": {
"name": "L1. LCM Guess",
"description": {
"content": "_This is an interactive problem._ There is a *hidden* permutation $P$ of length $n$ and you have to find it. For this, you have to choose *two different* integers $i$ and $j$, and the jury will give ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 12000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFL1"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_This is an interactive problem._\n\nThere is a *hidden* permutation $P$ of length $n$ and you have to find it. For this, you have to choose *two different* integers $i$ and $j$, and the jury will give ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"_This is an interactive problem._\\n\\nThere is a *hidden* permutation $P$ of length $n$ and you have to find it. For this, you have to choose *two different* integers $i...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the length of the hidden permutation $ P = (P_1, P_2, \\dots, P_n) $, where $ P $ is a bijection from $ \\{1, 2, \\dots, n\\} $ to $ \\{1, 2, \\dots, n\\} $. \n\n...",
"is_translate": false,
"language": "Formal"
}
]
}