trang chủ / đề bài / icpcwf19_a

Gạch azulejo

Đề bài

Mô tả

Hai nghệ nhân gốm Maria và João sắp mở một cửa hàng azulejo nhỏ ở Porto. Azulejo là những viên gạch gốm tuyệt đẹp đã làm nên danh tiếng của Bồ Đào Nha. Maria và João muốn bày một tủ kính thật bắt mắt, nhưng vì cửa hàng chật nên họ phải xếp các mẫu gạch thành hai hàng trên cùng một kệ.

Mỗi viên gạch của João (hàng sau) có đúng một viên gạch của Maria (hàng trước) đặt ngay trước nó, và mỗi viên gạch của Maria có đúng một viên gạch của João đặt ngay sau nó. Các viên gạch làm thủ công này có nhiều kích thước khác nhau, và điều quan trọng là mỗi viên ở hàng sau phải cao hơn hẳn viên ở ngay trước nó, để người đi đường nhìn thấy được cả hai.

Để tiện cho khách mua, các viên gạch trong mỗi hàng được xếp theo giá không giảm từ trái sang phải. Các viên cùng giá có thể xếp theo thứ tự bất kỳ, miễn là thỏa điều kiện nhìn thấy ở trên.

Hãy tìm một cách sắp thứ tự các viên gạch trong mỗi hàng thỏa mãn các ràng buộc này, hoặc cho biết không tồn tại cách sắp như vậy.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số viên gạch trong mỗi hàng. Bốn dòng tiếp theo, mỗi dòng chứa n số nguyên; hai dòng đầu mô tả hàng sau, hai dòng cuối mô tả hàng trước. Các viên gạch trong mỗi hàng được đánh số từ 1 đến n theo thứ tự xuất hiện trong input.

Trong mỗi cặp dòng, dòng thứ nhất chứa n số nguyên p1,…,pn, trong đó pi là giá của viên gạch số i trong hàng đó; dòng thứ hai chứa n số nguyên h1,…,hn, trong đó hi là chiều cao của viên gạch số i trong hàng đó.

Dữ liệu ra

Nếu có cách sắp hợp lệ, in ra hai dòng, mỗi dòng gồm n số nguyên là một hoán vị của các số hiệu viên gạch từ 1 đến n. Dòng thứ nhất là thứ tự các viên gạch hàng sau, dòng thứ hai là thứ tự các viên gạch hàng trước (từ trái sang phải). Nếu có nhiều cặp hoán vị thỏa mãn, in ra cặp nào cũng được.

Nếu không tồn tại cách sắp, in ra impossible.

Ràng buộc

  • 1≤n≤5·105.
  • 1≤pi≤109, 1≤hi≤109.

Ví dụ

Input Output Giải thích
4
3 2 1 2
2 3 4 3
2 1 2 1
2 2 1 3
3 2 4 1
4 2 1 3
Hàng sau (giá, cao) theo thứ tự in ra: (1,4),(2,3),(2,3),(3,2). Hàng trước: (1,3),(1,2),(2,2),(2,1). Giá mỗi hàng không giảm, và ở mỗi vị trí viên hàng sau cao hơn: 4>3, 3>2, 3>2, 2>1.
2
1 2
2 3
2 8
2 1
impossible Theo giá, hàng sau buộc phải là viên 1 (giá 1, cao 2) rồi viên 2 (giá 2, cao 3), hàng trước buộc phải là viên 1 (giá 2, cao 2) rồi viên 2 (giá 8, cao 1). Ở vị trí đầu tiên, viên hàng sau cao 2 không cao hơn viên hàng trước cao 2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0