[CEOI 2013] 有轨电车 / Tram

Luogu

IDLGP9270

Time1000ms

Memory256MB

DifficultyP4

2013CEOI（中欧）

给定一系列事件，每个事件都是乘客进入或离开电车。你需要输出这位乘客进入时他会坐在哪里。电车一开始是空的。输入中有 $m$ 个事件，按事件发生的顺序编号为 $1$ 到 $m$。有两种事件：`E` 类事件表示乘客进入有轨电车，而 `L` 类事件则表示乘客离开有轨电车。对于类型为 `L` 的事件，还给出了一个整数 $p$，它表示在该事件中离开的乘客是在**事件** $p$ 中进入的乘客。测试数据确保每当乘客试图进入电车时，电车中至少有一个空位。 ## Input 第一行输入包含两个整数 $n$ 和 $m$。接下来 $m$ 行，其中第 $i$ 行表示事件 $i$ 的内容，首先输入一个字符 `E` 或 `L`，当字符是 `L` 时再输入一个数 $p_i$，保证事件 $p_i$ 的类型一定是 `E`。 ## Output 输出中的行数应等于输入中 `E` 类事件的数量。对于第 $i$ 个类型为 `E` 的事件，在第 $i$ 行上输出该乘客选择的座位号 $r,c$（行和列），中间用一个空格隔开。 [samples] ## Background 翻译自 [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。在萨格勒布运营的电车的座位就像一个 $n$ 行 $2$ 列的网格，两个座位之间的距离，是相应网格正方形中心之间的欧几里得距离（直线距离）。大多数乘客在使用公共交通工具时会社恐，也就是说，当乘客进入电车时，会选择一个没有人坐的座位，并且该座位与最近的座位的距离尽可能大。如果有多个这样的座位，他们总是会选择一个行号较小的座位（因为这样他不需要走太远）。如果仍然有多个这种座位，他们会选择列号较小（即列号为 $1$）的座位。乘客选择座位后，会一直坐在那里，直到他离开电车。如果电车是空的，进入的乘客将始终选择第 $1$ 排第 $1$ 列的座位。 ## Note 对于 $25\%$ 的数据，$n,m\le150$。对于 $45\%$ 的数据，$n\le1500$。对于 $65\%$ 的数据，$m\le1500$。对于 $100\%$ 的数据，$n\le150000,m\le30000$。前三个测试点是样例。

Samples

Input #1

3 7
E
E
E
L 2
E
L 1
E

Output #1

Input #2

13 9
E
E
E
E
E
E
E
E
E

Output #2

Input #3

10 9
E
E
E
E
L 3
E
E
L 6
E

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2013] 有轨电车 / Tram",
    "description": {
      "content": "给定一系列事件，每个事件都是乘客进入或离开电车。你需要输出这位乘客进入时他会坐在哪里。电车一开始是空的。 输入中有 $m$ 个事件，按事件发生的顺序编号为 $1$ 到 $m$。有两种事件：`E` 类事件表示乘客进入有轨电车，而 `L` 类事件则表示乘客离开有轨电车。对于类型为 `L` 的事件，还给出了一个整数 $p$，它表示在该事件中离开的乘客是在**事件** $p$ 中进入的乘客。 测试数据",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9270"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一系列事件，每个事件都是乘客进入或离开电车。你需要输出这位乘客进入时他会坐在哪里。电车一开始是空的。\n\n输入中有 $m$ 个事件，按事件发生的顺序编号为 $1$ 到 $m$。有两种事件：`E` 类事件表示乘客进入有轨电车，而 `L` 类事件则表示乘客离开有轨电车。对于类型为 `L` 的事件，还给出了一个整数 $p$，它表示在该事件中离开的乘客是在**事件** $p$ 中进入的乘客。\n\n测试数据...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments