Có thể bạn từng nghe về Tensor Processing Unit của Google, loại chip dùng để xây dựng mạng nơ-ron. Tuy nhiên, còn một lĩnh vực nghiên cứu sâu sắc và quan trọng hơn cả học máy: sắp xếp!

Chúng tôi đang phát triển một con chip đặc biệt tên Sorting Permutation Unit, có thể áp dụng hoán vị lên mảng số nguyên rất nhanh. Một hoán vị là một thứ tự của \(n\) số nguyên dương đầu tiên \(p_1,p_2,\ldots,p_n\); áp dụng nó lên mảng \(a_1,a_2,\ldots,a_n\) sẽ cho mảng mới \(a_{p_1},a_{p_2},\ldots,a_{p_n}\). Ví dụ, áp dụng hoán vị 3 1 2 4 lên mảng 99 234 45 800 cho 45 99 234 800.

Tuy nhiên, biểu diễn hoán vị trong phần cứng rất tốn kém, nên bộ xử lý chỉ được dùng nhiều nhất \(P\) hoán vị khác nhau. Bạn phải giúp chọn các hoán vị đó.

Cho \(K\) mảng, mỗi mảng gồm \(N\) số nguyên. Trước hết, bạn chỉ định không quá \(P\) hoán vị kích thước \(N\) tùy ý. Sau đó, với mỗi mảng đầu vào, cung cấp một dãy không quá \(S\) chỉ thị; mỗi chỉ thị là một hoán vị trong tập đã khai báo. Áp dụng các chỉ thị theo đúng thứ tự phải cho một mảng được sắp không giảm. Trong mỗi dãy chỉ thị, mỗi hoán vị có thể được dùng không lần, một lần hoặc nhiều lần, và các lần dùng không nhất thiết liên tiếp.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng bốn số nguyên \(P,S,K,N\): số hoán vị tối đa được phép khai báo, số chỉ thị tối đa để sắp mỗi mảng, số mảng và số phần tử trong mỗi mảng. Tiếp theo là \(K\) dòng, mỗi dòng gồm \(N\) số nguyên \(A_{i1},A_{i2},\ldots,A_{iN}\); \(A_{ij}\) là giá trị thứ \(j\) của mảng thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, trước tiên in theo thứ tự:

• Một dòng Case #x:, với x là số thứ tự bộ test (bắt đầu từ 1).
• Một dòng chứa số nguyên \(P'\), với \(1\le P'\le P\): số hoán vị bạn chọn.
• \(P'\) dòng, dòng thứ \(i\) chứa \(N\) số \(p_{i1},p_{i2},\ldots,p_{iN}\) của hoán vị thứ \(i\).

Sau đó in thêm \(K\) dòng chỉ thị. Dòng thứ \(i\) bắt đầu bằng \(S'\), với \(0\le S'\le S\), rồi là \(S'\) số \(X_1,X_2,\ldots,X_{S'}\), trong đó \(1\le X_k\le P'\). \(X_k\) cho biết chỉ thị thứ \(k\) áp dụng hoán vị thứ \(X_k\) trong danh sách đã khai báo (đánh số từ 1). Dãy chỉ thị phải biến mảng đầu vào thứ \(i\) thành chính các phần tử của nó theo thứ tự không giảm.

Ràng buộc

• \(1\le T\le10\).
• \(S=450\).
• \(1\le K\le30\).
• \(2\le N\le50\).
• \(1\le A_{ij}\le1000\) với mọi \(i,j\).

Phân nhóm

Test Set 1 (Visible): \(P=20\).

Test Set 2 (Hidden): \(P=5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
20 450 4 3
10 10 11
17 4 1000
999 998 997
10 10 11
20 450 5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

Case #1:
2
3 1 2
2 1 3
0
1 2
2 2 1
1 2
Case #2:
1
5 1 2 3 4
0
1 1
2 1 1
3 1 1 1
4 1 1 1 1

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Sorting Permutation Unit.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.