L2. LCM Guess II

Codeforces

IDCFL2

Time12000ms

Memory256MB

Difficulty—

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 $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 $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. [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

_这是一个交互式问题。_ 存在一个长度为 $n$ 的*隐藏*排列 $P$，你需要找出它。为此，你需要选择*两个不同的*整数 $i$ 和 $j$，裁判会返回 $"lcm"(P_i, P_j)$。你最多可以进行 $n + 100$ 次查询以猜出 $P$。排列是由 $1$ 到 $n$ 中 $n$ 个不同整数按任意顺序组成的数组。例如，$[ 3, 1, 2, 5, 4 ]$ 是一个排列，但 $[ 1, 2, 1 ]$ 不是排列（数组中 1 出现了两次），$[ 2, 1, 4 ]$ 也不是排列（$n = 3$，但数组中出现了 4）。一个整数 $3 lt.eq n lt.eq 10^5$：*隐藏*排列 $P$ 的长度。然后交互开始。读取排列长度 $n$ 后，交互协议如下：在打印查询或答案后，请务必在行末输出换行符并刷新输出。否则，你将获得 *Idleness limit exceeded*。为此，请使用： ## Input 一个整数 $3 lt.eq n lt.eq 10^5$：*隐藏*排列 $P$ 的长度。然后交互开始。 ## Interaction 读取排列长度 $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 结果。 [samples] ## Note 在打印查询或答案后，请务必在行末输出换行符并刷新输出。否则，你将获得 *Idleness limit exceeded*。为此，请使用： *fflush(stdout)* 或 *cout.flush()* 在 C++ 中 *fflush(stdout)* 在 C 中 *System.out.flush()* 在 Java 中 *stdout.flush()* 在 Python 中

**Definitions** Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 10^5 $. Let $ P = (P_1, P_2, \dots, P_n) $ be a hidden permutation of $ \{1, 2, \dots, n\} $. **Constraints** You may query pairs $ (i, j) $ with $ 1 \leq i < j \leq n $, and receive $ \mathrm{lcm}(P_i, P_j) $. Total number of queries must not exceed $ n + 100 $. **Objective** Reconstruct the permutation $ P $ using at most $ n + 100 $ queries of the form $ \mathrm{lcm}(P_i, P_j) $.

API Response (JSON)

{
  "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 ...",
      "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 ]$ 是一个排列，但 $[...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments