Masala C
Coordinates on a Plane
On a plane are n points \(x_i,y_i\) with integer coordinates between 0 and \(10^6\). The distance between the two points with numbers a and b is said to be the following value:
\[dist(a,b) = |x_a - x_b| + |y_a - y_b|\](the distance calculated by such formula is called Manhattan distance).
We call a hamiltonian path to be some permutation pi of numbers from 1 to n. We say that the length of this path is value .
\[∑ ^ {n-1} _ {i=1} 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.
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 and y_i (0 ≤ x_i, y_i ≤ 10^6)\).
It is guaranteed that no two points coincide.
Print the permutation of numbers \(p_i\) from 1 to n — the sought Hamiltonian path. The permutation must meet the inequality
\[ ∑ ^ {n-1} _ {i=1} dist(p_i, p_{i+1}) <= 25 * 10^8 \]If there are multiple possible answers, print any of them.
It is guaranteed that the answer exists.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 0 7 8 10 3 4 5 0 9 12 |
4 3 1 2 5 |
In the sample test the total distance is:
\[dist(4,3) + dist(3,1) + dist(1,2) + 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
Telegram kanalimizga obuna bo'ling