← 返回题目列表

AtCoder · abc448_f

F. 正宗旅行商问题

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

有 N 位置编号 1 to N 在二维平面上。地点 i 位于坐标处 (X_i, Y_i).
您将从以下位置开始 1,访问每个位置一次,然后返回该位置 1.
移动地点 i 到位置 j 需要 \vert X_i - X_j \vert + \vert Y_i - Y_j \vert 秒。
输出访问所有位置并返回位置的路线 1 内 10^{10} 从位置开始的秒数 1。保证在给定的约束下至少存在一条这样的路由。

约束

  • 1 \leq N \leq 6 \times 10^4
  • 0 \leq X_i \leq 2 \times 10^7
  • 0 \leq Y_i \leq 2 \times 10^7
  • (X_i, Y_i) \neq (X_j, Y_j) if i \neq j
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

输出

让 p_i 是 i访问过的第一个位置 (1 \leq i \leq N),并按以下格式输出您的答案。

p_1 p_2 \dots p_N

如果满足以下所有条件,则认为您的答案是正确的。

  • (p_1, p_2, \dots, p_N) 是一个排列 (1, 2, \dots, N).
  • p_1 = 1
  • 出租 d(i, j) 是从位置移动所需的秒数 i 到位置 j, \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1} ) \leq 10^{10}.

如果有多个有效答案,则接受其中任何一个。


示例输入 1

3
0 6
3 5
2 4

示例输出 1

1 3 2

\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10,因此输出满足条件。


示例输入 2

10
9706344 19786176
19341349 15565412
5711023 19068083
12521132 14054301
14767612 17088029
14961700 18526945
13801766 5740101
6581153 8643675
13176196 16586661
4086263 5172719

示例输出 2

1 5 2 6 4 7 9 8 3 10