{"problem":{"name":"L2. LCM Guess II","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":"CFL2"},"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 $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 $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 $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":"_这是一个交互式问题。_\n\n存在一个长度为 $n$ 的*隐藏*排列 $P$，你需要找出它。为此，你需要选择*两个不同的*整数 $i$ 和 $j$，裁判会返回 $\"lcm\"(P_i, P_j)$。\n\n你最多可以进行 $n + 100$ 次查询以猜出 $P$。\n\n排列是由 $1$ 到 $n$ 中 $n$ 个不同整数按任意顺序组成的数组。例如，$[ 3, 1, 2, 5, 4 ]$ 是一个排列，但 $[ 1, 2, 1 ]$ 不是排列（数组中 1 出现了两次），$[ 2, 1, 4 ]$ 也不是排列（$n = 3$，但数组中出现了 4）。\n\n一个整数 $3 lt.eq n lt.eq 10^5$：*隐藏*排列 $P$ 的长度。然后交互开始。\n\n读取排列长度 $n$ 后，交互协议如下：\n\n在打印查询或答案后，请务必在行末输出换行符并刷新输出。否则，你将获得 *Idleness limit exceeded*。为此，请使用：\n\n## Input\n\n一个整数 $3 lt.eq n lt.eq 10^5$：*隐藏*排列 $P$ 的长度。然后交互开始。\n\n## Interaction\n\n读取排列长度 $n$ 后，交互协议如下：要获得 $\"lcm\"(P_i, P_j)$，请以格式 $? \" \"mathtt(i) \" \"mathtt(j)$ 输出查询，其中 $1 lt.eq i eq.not j lt.eq n$。你最多可以进行 $n + 100$ 次查询。当你找到 $P$ 时，以格式 $! \" \"mathtt(P)_1 \" \"mathtt(P)_2 \" \"dots.h \" \"mathtt(P)_n$ 输出 $P$。输出排列不计入 $n + 100$ 次操作中。在首次出现不符合给定格式的查询时，你将收到 $-1$，此时应立即退出以获得 Presentation error 结果。\n\n[samples]\n\n## Note\n\n在打印查询或答案后，请务必在行末输出换行符并刷新输出。否则，你将获得 *Idleness limit exceeded*。为此，请使用：\n*fflush(stdout)* 或 *cout.flush()* 在 C++ 中\n*fflush(stdout)* 在 C 中\n*System.out.flush()* 在 Java 中\n*stdout.flush()* 在 Python 中","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 10^5 $.  \nLet $ P = (P_1, P_2, \\dots, P_n) $ be a hidden permutation of $ \\{1, 2, \\dots, n\\} $.  \n\n**Constraints**  \nYou may query pairs $ (i, j) $ with $ 1 \\leq i < j \\leq n $, and receive $ \\mathrm{lcm}(P_i, P_j) $.  \nTotal number of queries must not exceed $ n + 100 $.  \n\n**Objective**  \nReconstruct the permutation $ P $ using at most $ n + 100 $ queries of the form $ \\mathrm{lcm}(P_i, P_j) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFL2","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}