[ROI 2018] Quantum teleportation

Luogu

IDLGP9289

Time4000ms

Memory512MB

DifficultyP7

2018Special JudgeROI（俄罗斯）

在一个平面直角坐标系上有编号为 $1\dots k$ 的 $k$ 块 CPU。每块 CPU 的位置可以用平面上的坐标来表示。$1$ 号 CPU 位于 $(1,1)$，$k$ 号 CPU 位于 $(n,m)$。保证所有 CPU 均位于整点上，且对于每块 CPU 的坐标 $(x_i, y_i)$，保证 $1 \le x_i \le n, 1 \le y_i \le m$。 $i$ 号 CPU 通过总线将一笔数据传输到 $j$ 号 CPU 的耗时为 ${2^{\max(|x_{{i}}-x_{{j}}|,|y_{{i}}-y_{{j}}|)}}$ 个单位时间。试求：要将数据从 $1$ 号 CPU 传送到 $k$ 号 CPU，至少需要多久，并给出一组方案。 ## Input 第一行三个整数 $n,m,k$。以下 $k$ 行，每行两个整数 $x_i,y_i$。 ## Output 第一行一个整数 $L$，表示最快的方案中要经过多少块 CPU。第二行 $L$ 个整数，表示依次经过的 CPU。如果存在多组路径使耗时最少，输出任意一种即可。 [samples] ## Background 译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Квантовая телепортация ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf)([Quantum teleportation](https://codeforces.com/gym/102147/problem/C))。 ## Note 对于所有的数据，$2 \leq n,m,k \leq 10000$。 | 子任务编号 | $n,m,k$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $2 \leq n,m,k \leq 20$ | 无 | | $2$ | $2 \leq n,m,k \leq 500$ | 无 | | $3$ | $2 \leq n,m,k \leq 10000$ | 每行、每列只有一个 CPU | | $4$ | $2 \leq n,m,k \leq 10000$ | 无 |

Samples

Input #1

Output #1

3
1 2 3

Input #2

Output #2

5
1 6 2 8 9

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2018] Quantum teleportation",
    "description": {
      "content": "在一个平面直角坐标系上有编号为 $1\\dots k$ 的 $k$ 块 CPU。 每块 CPU 的位置可以用平面上的坐标来表示。$1$ 号 CPU 位于 $(1,1)$，$k$ 号 CPU 位于 $(n,m)$。保证所有 CPU 均位于整点上，且对于每块 CPU 的坐标 $(x_i, y_i)$，保证 $1 \\le x_i \\le n, 1 \\le y_i \\le m$。 $i$ 号 CPU 通",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9289"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在一个平面直角坐标系上有编号为 $1\\dots k$ 的 $k$ 块 CPU。\n\n每块 CPU 的位置可以用平面上的坐标来表示。$1$ 号 CPU 位于 $(1,1)$，$k$ 号 CPU 位于 $(n,m)$。保证所有 CPU 均位于整点上，且对于每块 CPU 的坐标 $(x_i, y_i)$，保证 $1 \\le x_i \\le n, 1 \\le y_i \\le m$。\n\n$i$ 号 CPU 通...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments