Hamilton Path

Xem dạng PDF

Gửi bài giải


Điểm: 0,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
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

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 1
    doantronganh2008  đã bình luận lúc 27, Tháng 5, 2024, 9:54

    hi


  • -51
    ngokhanh  đã bình luận lúc 13, Tháng 10, 2023, 8:06

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.