← 返回题目列表

Codeforces · 576/C

C. 平面上的点

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

平面上有 n 个点 (xi, yi),其整数坐标在 0 到 106 之间。编号为 a 和 b 的两点之间的距离被称为以下值:$$\operatorname{dist}(a,b)=|x_{a}-x_{b}|+|y_{a}-y_{b}|$$(通过该公式计算的距离称为曼哈顿距离)。

我们将哈密顿路径称为从 1 到 n 的数字的某种排列 pi。我们说这条路径的长度是值$$\sum_{i=1}^{n-1} \text{dist}(p_i, p_{i+1})$$。

找到一些长度不超过 25 × 108 的哈密顿路径。请注意,您不必最小化路径长度。

输入

第一行包含整数 n (1 ≤ n ≤ 106)。

第 i + 1 行包含第 i 个点的坐标:xi 和 yi (0 ≤ xi, yi ≤ 106)。

保证没有两点重合。

输出

打印数字 pi 从 1 到 n 的排列 — 寻找的哈密顿路径。排列必须满足不等式 $${ \sum _ { i = 1 } ^ { n - 1 } \operatorname { d i s t } ( p _ { i }, p _ { i + 1 } ) } \leq 2 5 \times 1 0 ^ { 8 }$$。

如果有多个可能的答案,请打印其中任何一个。

保证答案存在。

示例

输入 #1

5
0 7
8 10
3 4
5 0
9 12

输出 #1

4 3 1 2 5

注意

在样本测试中,总距离为:

$$\text{dist}(4,3)+\text{dist}(3,1)+\text{dist}(1,2)+\text{dist}(2,5)=$$

(|5 - 3| + |0 - 4|) + (|3 - 0| + |4 - 7|) + (|0 - 8| + |7 - 10|) + (|8 - 9| + |10 - 12|) = 2 + 4 + 3 + 3 + 8 + 3 + 1 + 2 = 26