C. Closestools of Orz Pandas

Codeforces

IDCF10287C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There is a restroom for male Orz Pandas with $n$ closestools, labeled $1, 2, \\\\cdots, n$. The distance between the closestool $i$ and the closestool $j$ is $| i -j |$. The Orz Pandas are somewhat self-closed. When an Orz Panda enters the restroom, he will choose a closestool $x$, to make the distance between $x$ and any other closestools already occupied by another Orz Panda as large as possible. If there are mulitple closestools satisifying this condition, the Orz Panda will choose the one with the smallest label. Please write a program to simulate the operation of this restroom. There are multiple test cases. Please process until EOF. For each test case, the first line contains two integers $n$ and $m$, where $n$ is the number of closestools, and $m$ is the number of operations. Each of the next $m$ lines contains an operation. An operation may be one of the following: It's guaranteed that $1 <= n <= 10^9$, $1 <= m <= 10^5$, and the sum of $m$ in all test cases will not exceed $10^6$. For each type _2_ operation, it's guaranteed that $x$ is unique and the $x$-th operation is always a previous type _1_ operation. It's guaranteed that the number of Orz Pandas in the restroom will not exceed $n$ at any time. For each type _1_ operation, output one line, containing the label of the closestool the entering Orz Panda will choose. ## Input There are multiple test cases. Please process until EOF.For each test case, the first line contains two integers $n$ and $m$, where $n$ is the number of closestools, and $m$ is the number of operations. Each of the next $m$ lines contains an operation. An operation may be one of the following: _1_: an Orz Panda enters the restroom _2 x_: the Orz Panda entered the restroom at the $x$-th operation leaves the restroom It's guaranteed that $1 <= n <= 10^9$, $1 <= m <= 10^5$, and the sum of $m$ in all test cases will not exceed $10^6$. For each type _2_ operation, it's guaranteed that $x$ is unique and the $x$-th operation is always a previous type _1_ operation. It's guaranteed that the number of Orz Pandas in the restroom will not exceed $n$ at any time. ## Output For each type _1_ operation, output one line, containing the label of the closestool the entering Orz Panda will choose. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of objects. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing the values of the objects. **Game Rule** At each move, a player selects an object $ a_i $ (not yet eliminated) and earns a score equal to $ a_i \times (\text{number of adjacent remaining objects at the time of elimination}) $. After elimination, the object is removed, and the sequence is compacted (adjacent objects become neighbors). The game ends when all objects are eliminated. **Objective** Maximize the total score over all possible elimination orders. Compute: $$ \max_{\sigma \in S_n} \sum_{k=1}^{n} a_{\sigma(k)} \cdot c_k(\sigma) $$ where $ \sigma $ is a permutation of elimination order, and $ c_k(\sigma) $ is the number of adjacent remaining objects just before eliminating $ a_{\sigma(k)} $.

API Response (JSON)

{
  "problem": {
    "name": "C. Closestools of Orz Pandas",
    "description": {
      "content": "There is a restroom for male Orz Pandas with $n$ closestools, labeled $1, 2, \\\\\\\\cdots, n$. The distance between the closestool $i$ and the closestool $j$ is $| i -j |$. The Orz Pandas are somewhat s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10287C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a restroom for male Orz Pandas with $n$ closestools, labeled $1, 2, \\\\\\\\cdots, n$. The distance between the closestool $i$ and the closestool $j$ is $| i -j |$.\n\nThe Orz Pandas are somewhat s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of objects.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing the values of the objects.\n\n**Game Rule**  \nAt...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments