2535: CF576 - C. Points on Plane
[Creator : ]
Description
On a plane arenpoints $(x_i,y_i)$ with integer coordinates between $0$ and $10^6$. The distance between the two points with numbersaandbis said to be the following value: $\text{dist}(a,b)=|x_a-x_b|+|y_a-y_b|$ (the distance calculated by such formula is calledManhattan distance).
We call a hamiltonian path to be some permutation $p_i$ of numbers from $1$ to $n$. We say that the length of this path is value $\sum_{i=1}^{n-1} \text{dist}(p_i,p_{i+1})$.
Find some hamiltonian path with a length of no more than $25×10^8$. Note that you do not have to minimize the path length.
Find some hamiltonian path with a length of no more than $25×10^8$. Note that you do not have to minimize the path length.
Input
The first line contains integer $n\ (1≤n≤10^6)$.
The $i+1$-th line contains the coordinates of the $i$-th point: $x_i,y_i\ (0≤x_i,y_i≤10^6)$.
It is guaranteed that no two points coincide.
The $i+1$-th line contains the coordinates of the $i$-th point: $x_i,y_i\ (0≤x_i,y_i≤10^6)$.
It is guaranteed that no two points coincide.
Output
Print the permutation of numbers $p_i$ from $1$ to $n$ − the sought Hamiltonian path. The permutation must meet the inequality $\sum_{i=1}^{n-1} \text{dist}(p_i,p_{i+1})\leq 25\times 10^8$.
If there are multiple possible answers, print any of them.
It is guaranteed that the answer exists.
Sample 1 Input
5
0 7
8 10
3 4
5 0
9 12
Sample 1 Output
4 3 1 2 5
test the total distance is:
(|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.