/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
2 次元平面上に 1 から N の番号がついた N カ所の地点があります。地点 i は座標 (X_i, Y_i) にあります。
あなたは地点 1 を出発して全ての地点をちょうど 1 回ずつ巡回して再び地点 1 に戻ることにしました。
ここで、地点 i から地点 j へ移動するには \vert X_i - X_j \vert + \vert Y_i - Y_j \vert 秒かかります。
地点 1 を出発してから 10^{10} 秒以内に全ての地点を巡回して再び地点 1 に戻ることができる経路を出力してください。なお、制約下においてこの条件を満たす経路が少なくとも 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
- i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j)
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
i (1 \leq i \leq N) 番目に訪問する地点を p_i として以下の形式で答えを出力せよ。
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
Score : 525 points
Problem Statement
There are N locations numbered 1 to N on a two-dimensional plane. Location i is at coordinates (X_i, Y_i).
You will start from location 1, visit every location exactly once, and return to location 1.
Moving from location i to location j takes \vert X_i - X_j \vert + \vert Y_i - Y_j \vert seconds.
Output a route that visits all locations and returns to location 1 within 10^{10} seconds of starting from location 1. It is guaranteed that at least one such route exists under the given constraints.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Let p_i be the i-th location visited (1 \leq i \leq N), and output your answer in the following format.
p_1 p_2 \dots p_N
Your answer is considered correct if all of the following conditions are satisfied.
- (p_1, p_2, \dots, p_N) is a permutation of (1, 2, \dots, N).
- p_1 = 1
- Letting d(i, j) be the number of seconds it takes to move from location i to location j, \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1} ) \leq 10^{10}.
If there are multiple valid answers, any of them will be accepted.
Sample Input 1
3 0 6 3 5 2 4
Sample Output 1
1 3 2
\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10, so the output satisfies the condition.
Sample Input 2
10 9706344 19786176 19341349 15565412 5711023 19068083 12521132 14054301 14767612 17088029 14961700 18526945 13801766 5740101 6581153 8643675 13176196 16586661 4086263 5172719
Sample Output 2
1 5 2 6 4 7 9 8 3 10