trang chủ / đề bài / icpcwf17_l

Visual Python++

Đề bài

Mô tả

Trong ngôn ngữ lập trình Visual Python++ vừa được đề xuất gần đây, một khối lệnh được biểu diễn bằng một hình chữ nhật các ký tự có góc trên bên trái ở hàng r1, cột c1 và góc dưới bên phải ở hàng r2, cột c2. Mọi ký tự ở vị trí (r,c) với r1≤r≤r2 và c1≤c≤c2 được coi là thuộc khối đó. Trong các vị trí này, những vị trí có r=r1 hoặc r=r2 hoặc c=c1 hoặc c=c2 được gọi là đường viền của khối.

Các khối lệnh có thể lồng nhau (hình chữ nhật nằm trong hình chữ nhật khác) với số tầng tùy ý. Trong một chương trình đúng cú pháp, hai khối lệnh bất kỳ hoặc lồng nhau (một khối nằm trong khối kia), hoặc rời nhau (không chồng lên nhau). Trong cả hai trường hợp, đường viền của chúng không được có điểm chung.

Người lập trình không phải vẽ hết các hình chữ nhật trong một chương trình thông thường (việc đó quá mất thời gian, và khi đó Visual Python++ sẽ chẳng có cơ hội trở thành ngôn ngữ lập trình tiếp theo của ICPC). Người lập trình chỉ cần đặt một ký tự p ở góc trên bên trái của hình chữ nhật và một ký tự y ở góc dưới bên phải. Bộ phân tích cú pháp sẽ tự động ghép các góc tương ứng với nhau để dựng lại cấu trúc lồng nhau của chương trình.

Đội của bạn vừa nhận được hợp đồng năm giờ để phát triển phần này của bộ phân tích cú pháp.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n (1≤n≤105) là số cặp góc. Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên r và c (1≤r,c≤109), cho biết có một góc trên bên trái ở hàng r, cột c của chương trình cần phân tích. Tiếp theo là n dòng mô tả các góc dưới bên phải theo cùng cách đó. Mọi vị trí góc đều khác nhau.

Dữ liệu ra

In ra n dòng, mỗi dòng chứa một số nguyên. Số j ở dòng thứ i nghĩa là góc trên bên trái thứ i và góc dưới bên phải thứ j tạo thành một hình chữ nhật. Các góc trên bên trái và các góc dưới bên phải được đánh số riêng từ 1 đến n theo thứ tự xuất hiện trong dữ liệu vào. Kết quả phải là một hoán vị của các số từ 1 đến n sao cho cách ghép này cho các hình chữ nhật lồng nhau hợp lệ. Nếu có nhiều cách ghép hợp lệ, in ra cách nào cũng được. Nếu không tồn tại cách ghép nào, in ra syntax error.

Ràng buộc

  • 1≤n≤105.
  • 1≤r,c≤109 với mọi góc; 2n vị trí góc đôi một khác nhau.

Ví dụ

Input Output Giải thích
2
4 7
9 8
14 17
19 18
2
1
Khối (4,7) đến (19,18) chứa trọn khối (9,8) đến (14,17) ở bên trong, hai đường viền không chạm nhau.
2
4 7
14 17
9 8
19 18
1
2
Hai khối (4,7) đến (9,8) và (14,17) đến (19,18) rời nhau.
2
4 8
9 7
14 18
19 17
syntax error Với cả hai cách ghép, đường viền của hai hình chữ nhật cắt nhau.
3
1 1
4 8
8 4
10 6
6 10
10 10
syntax error Ví dụ cách ghép (1,1) với (10,10), (4,8) với (6,10), (8,4) với (10,6) có các góc (6,10) và (10,6) nằm trên đường viền của khối lớn; các cách ghép khác cũng đều không hợp lệ.

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