COCI 2019/2020 - Contest 2 - Slagalica

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 2
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cậu bé Fabian có một bộ đồ chơi xếp hình một chiều với ~N~ mảnh ghép. Cậu nhanh chóng nhận ra rằng mỗi mảnh sẽ thuộc một trong những kiểu như sau:

Ngoài ra, trong số ~N~ mảnh ghép này chỉ có duy nhất một mảnh thuộc kiểu ~5~ hoặc ~6~ (biên trái) và duy nhất một mảnh thuộc kiểu ~7~ hoặc ~8~ (biên phải).

Fabian muốn sắp xếp tất cả các mảnh ghép vào một hàng sao cho mảnh đầu (mảnh trái nhất) thuộc kiểu ~5~ hoặc ~6~ và mảnh cuối (mảnh phải nhất) thuộc kiểu ~7~ hoặc ~8~. Hai mảnh có thể đứng cạnh nhau khi và chỉ khi hai biên gần nhau của hai mảnh ghép có hình dạng khác nhau, nghĩa là, một biên có đầu nổi lên, biên còn lại là nơi lõm vào.

Việc lắp ráp bộ xếp hình này thật quá dễ dàng với Fabian nên cậu quyết định viết các con số nguyên dương đôi một khác nhau lên mỗi mảnh ghép. Bây giờ cậu muốn tìm ra cách sắp xếp có thứ tự từ điển nhỏ nhất. Cách xếp ~A~ có thứ tự từ điển nhỏ hơn cách xếp ~B~ nếu tồn tại vị trí ~i~ đầu tiên bên trái mà số thứ ~i~ của ~A~ (~A_i~) khác số thứ ~i~ của ~B~ (~B_i~), ~A_i~ < ~B_i~.

Lưu ý: Không được xoay các mảnh ghép.

Input

Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 10^5)~.

~N~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~X_i~ ~(1 \le X_i \le 8)~ và ~A_i~ ~(1 \le A_i \le 10^9)~ biểu diễn kiểu của mảnh ghép thứ ~i~ và số Fabian viết lên mảnh ghép đó. Các số ~A_i~ phân biệt.

Output

Nếu không tồn tại cách xếp bộ xếp hình, in ra ~-1~.

Trái lại, xuất ra dãy các số xuất hiện trên các mảnh ghép sao cho thứ tự từ điển của dãy được tìm thấy là nhỏ nhất.

Sample Input 1

5
1 5
2 7
2 3
8 4
6 1

Sample Output 1

1 3 7 5 4

Sample Input 2

3
5 1
7 2
4 3

Sample Output 2

1 3 2

Sample Input 3

5
2 5
2 7
2 3
8 4
6 1

Sample Output 3

-1

Subtask:

  • ~4~ test đầu có ~N \le 4~.

  • ~2~ test sau có ~N \le 10~.

  • ~4~ test sau đảm bảo input không tồn tại mảnh ghép thuộc kiểu ~2~ và ~3~.

  • ~10~ test sau input có nhiều nhất một mảnh thuộc kiểu ~1~ hoặc ~4~.

  • ~12~ test cuối cùng không có điều kiện gì thêm.

Lưu ý: Trường hợp trong một Subtask nào đó tồn tại cách xếp cho bộ xếp hình, nếu bạn xuất ra cách xếp đúng nhưng không phải cách xếp có thứ tự từ điển nhỏ nhất, bạn sẽ chỉ nhận được ~40\%~ số điểm của Subtask đó.

Giải thích ví dụ 1:

Chỉ có duy nhất ~2~ cách xếp:

Ta có thể thấy cách xếp thứ hai có thứ tự từ điển nhỏ hơn cách xếp thứ nhất. Vì vậy, cách xếp thứ hai là cách xếp có thứ tự từ điển nhỏ nhất.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.