{"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 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).\n\nOne integer $3 <= n <= 10^5 :$ The size of the *hidden* permutation $P$. Then, the interaction will start.\n\nAfter reading the length of the permutation $n,$ the interaction protocol is as follows : \n\nAfter 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:\n\n## Input\n\nOne integer $3 <= n <= 10^5 :$ The size of the *hidden* permutation $P$. Then, the interaction will start.\n\n## Interaction\n\nAfter 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. \n\n[samples]\n\n## Note\n\nAfter 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","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$ 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 \"}]}","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**Constraints**  \n1. $ 3 \\leq n \\leq 10^5 $  \n2. You may query at most $ 2n + 100 $ times.  \n3. Each query consists of two distinct indices $ i, j \\in \\{1, 2, \\dots, n\\} $, and returns $ \\mathrm{lcm}(P_i, P_j) $.  \n\n**Objective**  \nReconstruct the permutation $ P $ using at most $ 2n + 100 $ queries of the form $ \\mathrm{lcm}(P_i, P_j) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFL1","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}