Appraiser

AtCoder

IDarc184_a

Time2000ms

Memory256MB

Difficulty—

This problem is **interactive**, and the **judge is adaptive**. See the notes for details. **Also, the parameters in the problem statement are fixed at $N=1000$, $M=10$, $Q=950$.** There are $N$ coins numbered $1, 2, \dots, N$. Exactly $M$ of these coins are counterfeit. An appraiser can, in one appraisal, determine whether two coins are of the same type or different types. Specifically: * If the two coins are both genuine or both counterfeit, they are judged to be of the same type. * Otherwise, they are judged to be of different types. Identify all the counterfeit coins using at most $Q$ appraisals. ## Constraints * $\color{red}{N = 1000}$ * $\color{red}{M = 10}$ * $\color{red}{Q = 950}$ ## Interaction This is an interactive problem. Initially, receive $N$, $M$, and $Q$ from Standard Input: $N$ $M$ $Q$ Next, you can perform appraisals between $0$ and $Q$ times, inclusive, as follows. First, by outputting to Standard Output in the following format, you indicate that you are appraising coins $x$ and $y$. (Include a newline at the end.) ? $x$ $y$ Here, $x$ and $y$ must be distinct integers between $1$ and $N$, inclusive. In response, the judge system will reply with one of the following three responses. 0 If the response is `0`, it means that coins $x$ and $y$ are of the same type. 1 If the response is `1`, it means that coins $x$ and $y$ are of different types. \-1 If the response is `-1`, it means that the appraisal is invalid. Specifically, this response is given when at least one of the following conditions is met: * The outputted $x$ and $y$ does not satisfy the constraints. * The number of appraisals exceeds $Q$. If you receive this response, your program is considered incorrect. Terminate your program immediately. Finally, by outputting to Standard Output in the following format, you answer that coins $A_1, A_2, \dots, A_{M}$ are counterfeit. (Include a newline at the end.) ! $A_1$ $A_2$ $\dots$ $A_{M}$ Here, $A_i$ must be distinct integers between $1$ and $N$, inclusive. After this output, terminate your program immediately. If any of your outputs do not meet the specified format, your program will be considered incorrect. The judge will then respond with `-1`, so in that case, terminate your program immediately. [samples] ## Notes * **Every time you output, include a newline at the end and flush Standard Output.** Failure to do so may result in a verdict of TLE or WA. * After outputting your answer (or receiving `-1`), terminate your program immediately. Otherwise, the verdict is indeterminate. * Beware that unnecessary newlines are considered as malformed. * **The judge for this problem is adaptive.** That is, at any point, as long as consistency can be maintained, the judge may change which coins are counterfeit. See the sample interaction for details.

API Response (JSON)

{
  "problem": {
    "name": "Appraiser",
    "description": {
      "content": "This problem is **interactive**, and the **judge is adaptive**. See the notes for details.   **Also, the parameters in the problem statement are fixed at $N=1000$, $M=10$, $Q=950$.** There are $N$ coi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc184_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "This problem is **interactive**, and the **judge is adaptive**. See the notes for details.  \n**Also, the parameters in the problem statement are fixed at $N=1000$, $M=10$, $Q=950$.**\nThere are $N$ coi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments