Diễn tập


Submit solution

Points: 2 (partial)
Time limit: 1.0s
Memory limit: 488M

Author:
Problem type

Một hội nghị quốc tế quan trọng sắp được tổ chức tại Thủ đô. Kế hoạch đảm bảo an ninh được soạn thảo hết sức chu đáo.

Toàn bộ thành phố được xét như lưới ô vuông các cột được đánh số từ trái sang phải từ -∞ đến +∞, các hàng được đánh số từ dưới lên trên từ từ -∞ đến +∞. Khu vực diễn ra hội nghị là ô (0, 0). Mọi thiết bị bay không người lái (drone) đều bị cấm bay trong thời gian diễn ra hội nghị, nếu xuất hiện sẽ bị bắn hạ. Một khẩu pháo laser được bố trí tại ô (0, 0), cứ mỗi giây có thể phát một chùm laser công suất cao phá hủy một drone ở độ cao và khoảng cách bất kỳ. Để kiểm tra khả năng tác chiến người ta tiến hành một cuộc diễn tập với tình huống giả định là xuất hiện \(n\) drones (đánh số từ 1 đến \(n\)), drone thứ \(i\) \((1 \le i \le n)\) xuất hiện ở không phận thuộc ô \((x_i, y_i)\), cứ sau mỗi giây drone có thể chuyển sang không phận ô kề cạnh và hướng về phía ô (0, 0). Trên không phận một ô có thể có đồng thời nhiều drones.

Nhiệm vụ của bộ phận bảo vệ là không để cho drone nào vào được không phận ô (0, 0).

Hãy xác định trình tự các drones cần tiêu diệt. Trường hợp không thể thực hiện được nhiệm vụ đã nêu, đưa ra số -1.

Đầu vào

  • Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\)
  • Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa 2 số nguyên \(x_i\) và \(y_i\) \((|x_i|, |y_i| \le 10^5)\).

Đầu ra

In ra -1 hoặc dãy số nguyên xác định trình tự drones cần bắn hạ; trong trường hợp có nhiều phương án trả lời, hãy đưa ra phương án có thứ tự từ điển nhỏ nhất.

Ví dụ

Đầu vào

3
0 1
-2 3
2 2

Đầu ra

1 3 2

Comments


  • 1
    NgocAnh_CNTT3_K61  commented on April 8, 2021, 10:29 a.m.

    Em muốn hỏi đề ra là 'cứ sau mỗi giây drone có thể chuyển sang không phận ô kề cạnh hoặc kề đỉnh' thì ở đây ý là drone chỉ có thể đi ngang dọc hay đi chéo cũng được tính ạ? Nếu là trường hợp chỉ đi được ngang dọc thì hy vọng lần sau người ra đề viết rõ một tí.