Hamilton Path

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trên một mặt phẳng có n điểm có tọa độ nguyên ~(x_i, y_i)~ trong khoảng từ ~0~ đến ~10^6~. Khoảng cách giữa hai điểm có số thứ tự ~a~ và ~b~ là ~dist(a, b)~ được xác định như sau: ~|x_a - x_b| + |y_a - y_b|~ (khoảng cách tính bằng công thức này được gọi là khoảng cách Manhattan).

Chúng ta gọi một đường đi Hamiltonian là một hoán vị ~p_i~ của các số từ ~1~ đến ~n~. Chiều dài của đường đi này được tính theo công thức sau: $$\sum_{i=1}^{n-1}(dist(p_i, p_{i+1})) + dist(p_n, p_1)$$

Hãy tìm một đường đi Hamiltonian sao cho chiều dài của nó không vượt quá ~25 \times 10^8~. Lưu ý rằng bạn không cần tối ưu hóa chiều dài của đường đi.

Input

Dòng đầu tiên chứa số nguyên n ~(1 \leq n \leq 10^6)~.

Dòng thứ ~i+1~ chứa tọa độ của điểm thứ ~i~: ~x_i~ và ~y_i~ ~(0 \leq x_i, y_i \leq 10^6)~.

Đảm bảo rằng không có hai điểm nào trùng nhau.

Output

In ra hoán vị của các số ~p_i~ từ 1 đến ~n~ — đường đi Hamiltonian cần tìm.

Nếu có nhiều đáp án đúng, in bất kỳ một trong số chúng.

Đảm bảo rằng có ít nhất một đường đi thỏa mãn yêu cầu.

Sample Input 1

5
0 7
8 10
3 4
5 0
9 12

Sample Output 1

5 2 1 3 4

Comments

Please read the guidelines before commenting.



  • -25
    ngokhanh  commented on Oct. 13, 2023, 8:06 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.