JOI 2020 - Trại huấn luyện mùa xuân - Ngày 1

Thế vận hội sắp được tổ chức tại vương quốc JOI. Để chào đón các vận động viên từ khắp nơi trên thế giới, những tòa nhà dọc đường từ sân bay đến nơi lưu trú sẽ được trang trí. Có \(2N\) tòa nhà, được đánh số từ \(1\) đến \(2N\) theo thứ tự từ phía sân bay.

Tổng thống K phụ trách dự án trang trí. Ông kêu gọi người dân đề xuất các phương án và cuối cùng chọn ra hai phương án \(A\) và \(B\). Theo phương án \(A\), mức độ lộng lẫy của tòa nhà thứ \(i\) (\(1 \le i \le 2N\)) là \(A_i\); theo phương án \(B\), mức độ lộng lẫy của tòa nhà đó là \(B_i\).

Cả hai phương án đều rất tốt nên ông khó lựa chọn. Ông quyết định chọn một trong hai phương án cho từng tòa nhà. Để bảo đảm công bằng, đúng \(N\) tòa nhà phải dùng phương án \(A\) và \(N\) tòa nhà còn lại phải dùng phương án \(B\). Ngoài ra, để các vận động viên càng thêm hào hứng trên đường đến nơi lưu trú, mức độ lộng lẫy phải không giảm: gọi \(C_i\) là mức độ lộng lẫy của tòa nhà thứ \(i\), cần có \(C_i \le C_{i+1}\) với mọi \(1 \le i \le 2N-1\).

Hãy viết chương trình nhận số tòa nhà và mức độ lộng lẫy của từng tòa nhà trong mỗi phương án, xác định có thể chọn các phương án thỏa mãn yêu cầu hay không, và in ra một cách chọn nếu có.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N
A_1 A_2 ... A_{2N}
B_1 B_2 ... B_{2N}

Dữ liệu ra

Nếu không có cách chọn thỏa mãn yêu cầu, in ra -1.

Ngược lại, in ra xâu \(S\) có độ dài \(2N\) mô tả cách chọn. Ký tự thứ \(i\) (\(1 \le i \le 2N\)) của \(S\) là A nếu tòa nhà thứ \(i\) dùng phương án \(A\), và là B nếu dùng phương án \(B\). Nếu có nhiều cách chọn hợp lệ, có thể in ra một cách bất kỳ.

Ràng buộc

• \(1 \le N \le 500000\).
• \(1 \le A_i \le 10^9\) với mọi \(1 \le i \le 2N\).
• \(1 \le B_i \le 10^9\) với mọi \(1 \le i \le 2N\).

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm. Các ràng buộc bổ sung và số điểm của từng nhóm như sau:

1. \(11\) điểm: \(N \le 2000\).
2. \(89\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3
2 5 4 9 15 11
6 7 6 8 12 14

AABABB

2
1 4 10 20
3 5 8 13

BBAA

2
3 4 5 6
10 9 8 7

-1

6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78

BABBABAABABA

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, kỳ trại huấn luyện mùa xuân JOI 2019/2020, ngày thi thứ nhất (20/03/2020). Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bạn đã nghe đến công ty Just Odd Inventions, Ltd. chưa? Công ty này nổi tiếng với những phát minh kỳ lạ. Trong bài toán này, ta gọi công ty là JOI.

Công ty JOI đang tổ chức tiệc năm mới. Các nhân viên nướng \(N\) miếng thịt băm trên một vỉ nướng khổng lồ. Coi vỉ nướng là một bảng ô vuông kích thước \(10^9 \times 10^9\). Ký hiệu \((x,y)\) là ô ở cột thứ \(x\) từ trái sang và hàng thứ \(y\) từ dưới lên, với \(1 \le x,y \le 10^9\).

Các miếng thịt được đánh số từ \(1\) đến \(N\). Miếng thứ \(i\) (\(1 \le i \le N\)) nằm trên vùng hình chữ nhật có góc dưới bên trái là \((L_i,D_i)\) và góc trên bên phải là \((R_i,U_i)\). Các miếng thịt có thể chồng lên nhau.

Bạn là nhân viên mới của công ty JOI. Nhiệm vụ của bạn là chọn \(K\) ô trên vỉ và cắm các que tre vào tâm những ô đó, vuông góc với mặt vỉ. Để kiểm tra độ chín của một miếng thịt, phải có ít nhất một que được cắm vào một ô thuộc miếng thịt đó. Bạn cần kiểm tra tất cả các miếng thịt. Có thể cắm nhiều que vào cùng một ô, và cũng có thể cắm que vào một ô không có miếng thịt nào.

Cụ thể, hãy tìm \(K\) cặp số nguyên \((x_1,y_1),\ldots,(x_K,y_K)\), không nhất thiết đôi một khác nhau, thỏa mãn:

• Với mỗi \(i\) (\(1 \le i \le N\)), tồn tại \(j\) (\(1 \le j \le K\)) sao cho đồng thời \(L_i \le x_j \le R_i\) và \(D_i \le y_j \le U_i\).
• Với mỗi \(j\) (\(1 \le j \le K\)), có \(1 \le x_j \le 10^9\) và \(1 \le y_j \le 10^9\).

Hãy viết chương trình nhận vị trí các miếng thịt và số que tre, rồi tìm một cách cắm que thỏa mãn yêu cầu. Dữ liệu bảo đảm luôn tồn tại một cách chọn \(K\) ô như vậy.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N K
L_1 D_1 R_1 U_1
L_2 D_2 R_2 U_2
...
L_N D_N R_N U_N

Dữ liệu ra

In ra \(K\) dòng. Dòng thứ \(j\) (\(1 \le j \le K\)) chứa hai số \(x_j\) và \(y_j\), cách nhau bởi một dấu cách.

Nếu có nhiều cách cắm que thỏa mãn yêu cầu, có thể in ra một cách bất kỳ.

Ràng buộc

• \(1 \le N \le 200000\).
• \(1 \le K \le 4\).
• \(1 \le L_i \le R_i \le 10^9\) với mọi \(1 \le i \le N\).
• \(1 \le D_i \le U_i \le 10^9\) với mọi \(1 \le i \le N\).
• Luôn tồn tại \(K\) ô thỏa mãn các điều kiện trong đề bài.

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm. Các ràng buộc bổ sung và số điểm của từng nhóm như sau:

1. \(1\) điểm: \(N \le 2000\) và \(K=1\).
2. \(1\) điểm: \(N \le 2000\) và \(K=2\).
3. \(3\) điểm: \(N \le 2000\) và \(K=3\).
4. \(6\) điểm: \(N \le 2000\) và \(K=4\).
5. \(1\) điểm: \(K=1\).
6. \(3\) điểm: \(K=2\).
7. \(6\) điểm: \(K=3\).
8. \(79\) điểm: \(K=4\).

Ví dụ

4 2
2 1 3 3
1 2 4 3
6 1 7 4
5 3 7 5

2 2
7 4

3 3
1 1 1 1
1 2 1 2
1 3 1 3

1 1
1 2
1 3

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, kỳ trại huấn luyện mùa xuân JOI 2019/2020, ngày thi thứ nhất (20/03/2020). Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Căn phòng của Bitaro có hình tam giác vuông cân với độ dài mỗi cạnh góc vuông bằng \(N\). Một điểm trong phòng được biểu diễn bằng tọa độ \((x,y)\), thỏa mãn \(0 \le x \le N\), \(0 \le y \le N\) và \(x+y \le N\). Đỉnh góc vuông là gốc tọa độ; hai cạnh góc vuông nằm trên trục \(x\) và trục \(y\).

Một ngày nọ, Bitaro nhận thấy căn phòng đầy bụi. Ban đầu có \(M\) hạt bụi trong phòng. Hạt bụi thứ \(i\) (\(1 \le i \le M\)) nằm tại \((X_i,Y_i)\). Nhiều hạt bụi có thể nằm tại cùng một điểm.

Bitaro định dùng chổi để quét phòng. Ta coi chổi là một đoạn thẳng nằm trong phòng và gọi độ dài đoạn thẳng đó là bề rộng của chổi. Bitaro chỉ dùng chổi theo hai cách sau:

• Thao tác H: Đặt chổi song song với trục \(y\), với một đầu ở gốc tọa độ. Sau đó di chuyển chổi theo chiều dương của trục \(x\) xa nhất có thể trong phòng, luôn giữ chổi song song với trục \(y\) và một đầu nằm trên trục \(x\). Nếu bề rộng chổi là \(l\), hạt bụi ở \((x,y)\) thỏa mãn \(x<N-l\) và \(y \le l\) sẽ được đẩy đến \((N-l,y)\). Tại điểm đến có thể đã có các hạt bụi khác.
• Thao tác V: Đặt chổi song song với trục \(x\), với một đầu ở gốc tọa độ. Sau đó di chuyển chổi theo chiều dương của trục \(y\) xa nhất có thể trong phòng, luôn giữ chổi song song với trục \(x\) và một đầu nằm trên trục \(y\). Nếu bề rộng chổi là \(l\), hạt bụi ở \((x,y)\) thỏa mãn \(x \le l\) và \(y<N-l\) sẽ được đẩy đến \((x,N-l)\). Tại điểm đến có thể đã có các hạt bụi khác.

Có \(Q\) sự kiện lần lượt xảy ra trong phòng. Sự kiện thứ \(j\) (\(1 \le j \le Q\)) thuộc một trong bốn loại:

• Bitaro xác định tọa độ của hạt bụi thứ \(P_j\).
• Bitaro dùng chổi có bề rộng \(L_j\) để thực hiện thao tác H.
• Bitaro dùng chổi có bề rộng \(L_j\) để thực hiện thao tác V.
• Thêm một hạt bụi tại \((A_j,B_j)\). Nếu trước sự kiện này có \(c\) hạt bụi, hạt bụi mới được đánh số \(c+1\).

Hãy viết chương trình nhận độ dài cạnh góc vuông của căn phòng, tọa độ ban đầu của các hạt bụi và thông tin về các sự kiện, rồi xác định tọa độ các hạt bụi được hỏi.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N M Q
X_1 Y_1
...
X_M Y_M
(Sự kiện 1)
...
(Sự kiện Q)

Mỗi dòng (Sự kiện j) chứa hai hoặc ba số nguyên cách nhau bởi dấu cách. Gọi số nguyên đầu tiên là \(T_j\). Ý nghĩa của dòng đó như sau:

• Nếu \(T_j=1\), dòng chứa 1 P_j: xác định tọa độ của hạt bụi thứ \(P_j\) tại thời điểm xảy ra sự kiện thứ \(j\).
• Nếu \(T_j=2\), dòng chứa 2 L_j: dùng chổi có bề rộng \(L_j\) thực hiện thao tác H.
• Nếu \(T_j=3\), dòng chứa 3 L_j: dùng chổi có bề rộng \(L_j\) thực hiện thao tác V.
• Nếu \(T_j=4\), dòng chứa 4 A_j B_j: thêm một hạt bụi tại \((A_j,B_j)\).

Dữ liệu ra

Với mỗi sự kiện có \(T_j=1\), in ra một dòng chứa hoành độ và tung độ của hạt bụi thứ \(P_j\) tại thời điểm xảy ra sự kiện đó, theo đúng thứ tự các sự kiện.

Ràng buộc

• \(1 \le N \le 10^9\).
• \(1 \le M \le 500000\).
• \(1 \le Q \le 1000000\).
• \(0 \le X_i \le N\) với mọi \(1 \le i \le M\).
• \(0 \le Y_i \le N\) với mọi \(1 \le i \le M\).
• \(X_i+Y_i \le N\) với mọi \(1 \le i \le M\).
• Với mỗi sự kiện loại \(1\), \(P_j\) nằm từ \(1\) đến số hạt bụi có trong phòng khi sự kiện thứ \(j\) xảy ra.
• Với mỗi sự kiện loại \(2\) hoặc \(3\), \(0 \le L_j \le N-1\).
• Với mỗi sự kiện loại \(4\), \(0 \le A_j \le N\), \(0 \le B_j \le N\) và \(A_j+B_j \le N\).
• Có ít nhất một sự kiện có \(T_j=1\).

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm. Các ràng buộc bổ sung và số điểm của từng nhóm như sau:

1. \(1\) điểm: \(M \le 2000\) và \(Q \le 5000\).
2. \(10\) điểm: \(T_j \in \{1,2,4\}\) với mọi \(1 \le j \le Q\).
3. \(11\) điểm: \(T_j \in \{1,2,3\}\) với mọi \(1 \le j \le Q\); đồng thời \(X_i \le X_{i+1}\) và \(Y_i \ge Y_{i+1}\) với mọi \(1 \le i \le M-1\).
4. \(53\) điểm: \(T_j \in \{1,2,3\}\) với mọi \(1 \le j \le Q\).
5. \(25\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6 2 10
1 1
4 0
4 2 3
3 3
1 1
4 1 2
2 3
2 0
1 4
3 2
1 3
1 2

1 3
3 2
3 3
6 0

9 4 8
2 3
3 1
1 6
4 3
2 6
1 3
2 2
1 4
2 3
1 2
2 4
1 1

3 6
4 3
7 1
6 3

8 1 8
1 5
4 4 1
2 6
1 2
2 3
4 2 2
2 5
1 1
1 3

4 1
3 5
3 2

7 4 9
1 5
2 2
4 2
5 0
2 6
2 3
1 2
3 6
1 4
3 1
1 1
2 2
1 3

4 2
5 1
1 6
5 2

20 5 25
10 6
0 4
2 1
1 0
2 3
2 18
3 9
4 1 5
4 0 2
3 10
4 3 3
3 3
2 9
4 9 1
3 12
1 4
3 19
1 3
1 9
2 1
1 7
1 6
4 3 3
1 10
1 1
1 5
2 0
1 2
2 2
1 7

2 17
2 17
9 8
0 17
1 17
3 3
10 10
2 17
2 17
0 17

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, kỳ trại huấn luyện mùa xuân JOI 2019/2020, ngày thi thứ nhất (20/03/2020). Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.