Range Sums 2

AtCoder

IDarc192_c

Time2000ms

Memory256MB

Difficulty—

**This problem is interactive.** You are given a positive integer $N$. Snuke secretly holds a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ and a sequence $A=(A_1,A_2,\dots,A_N)$ of positive integers of length $N$. **It is guaranteed that $P_1<P_2$.** You may send up to $2N$ queries to Snuke. A query is of the following form: * Specify two **distinct** positive integers $s$ and $t$ with $1\leq s,t\leq N$, and you will be given the value of $\displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i$. Determine $P$ and $A$. ## Constraints * $3\leq N\leq 5000$ * $1\leq P_i\leq N$ $(1\leq i\leq N)$ * $P_i\ne P_j$ for $i\ne j$. * $P_1<P_2$ * $1\leq A_i\leq 10^9$ $(1\leq i\leq N)$ * $N$, $P_i$, and $A_i$ are integers. * $P$ and $A$ are fixed before the interaction with the judge. ## Input/output This problem is interactive. First, $N$ is given from Standard Input: $N$ Next, you may send at most $2N$ queries to Snuke. When sending a query by specifying two **distinct** positive integers $s,t$, output in the following format. Do not forget to include a newline at the end. ? $s$ $t$ After sending a query, you will receive a response from Snuke in the following format: $X$ Here, $X$ is an integer: * If $X\ne -1$, then $X$ is the value of $\displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i$. * If $X=-1$, then either $s,t$ do not satisfy the constraints or you have sent more than $2N$ queries. * In this case, your program is judged as incorrect and must terminate immediately. Once you have determined $P$ and $A$, output your answer in the following format. This output does not count as a query. ! $P_1$ $P_2$ $\dots$ $P_N$ $A_1$ $A_2$ $\dots$ $A_N$ **Note that $P_1<P_2$.** After this output, terminate your program immediately. If you output anything that does not follow the above formats, `-1` will be given as input. \-1 In that case, your program is judged as incorrect and must terminate immediately. [samples] ## Notes * **After every output, be sure to end with a newline and flush the standard output. Failure to do so may result in a TLE.** * When you output your answer, or receive `-1` from standard input, terminate your program immediately. Otherwise, the outcome is indeterminate. * Note that extra newlines may be considered as an output format error. * **The judge system for this problem is not adaptive.** That is, $P$ and $A$ are determined before the interaction with the judge and will not be changed at any point.

API Response (JSON)

{
  "problem": {
    "name": "Range Sums 2",
    "description": {
      "content": "**This problem is interactive.** You are given a positive integer $N$. Snuke secretly holds a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$ and a sequence $A=(A_1,A_2,\\dots,A_N)$ of positive ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc192_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**This problem is interactive.**\nYou are given a positive integer $N$.\nSnuke secretly holds a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$ and a sequence $A=(A_1,A_2,\\dots,A_N)$ of positive ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments