27792번 - Sorting Permutation Unit 서브태스크스페셜 저지다국어채점 준비 중

You may have heard of Google's Tensor Processing Units, which are used to build neural networks. However, there is one research area that is even deeper and more important than machine learning: sorting!

We are working on a special new chip called the Sorting Permutation Unit, which is very fast at applying permutations to arrays of integers. Formally, a permutation is an ordering of the first n positive integers

p₁, p₂, ..., p_n

and applying it to an array of n integers

a₁, a₂, ..., a_n

yields the new array

a_p1, a_p2, ..., a_pn.

For example, applying the permutation 3, 1, 2, 4 to the array 99, 234, 45, 800 would yield the new array 45, 99, 234, 800.

However, permutations are expensive to represent in the hardware, so the unit can only have access to at most P distinct permutations. We need your help figuring out what those permutations should be!

Given K arrays of N integers each, you must first specify up to P permutations (of size N) of your choice. Then, for each of those K input arrays, you must provide one sequence of up to S instructions (each of which is a permutation from your specified set). When the instructions in this sequence are applied, in the given order, to the array, they must yield an array sorted in nondecreasing order. In each of your K sequences of instructions, you may use each of your P permutations zero or more times (not necessarily consecutively).

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with four integers P, S, K, and N: the maximum number of permutations allowed, the maximum number of instructions you are allowed to use to sort each array, the number of arrays, and the number of integers in each array. Then, there are K more lines of N integers A_i1, A_i2, .., A_iN each, where the j-th integer on the i-th line, A_ij, represents the j-th value of the i-th array.

For each test case, first output the following, in this order:

• One line containing Case #x:, where x is the test case number (starting from 1).
• One line containing one integer P', where 1 ≤ P' ≤ P: the number of permutations you have chosen to use.
• P' lines, the i-th of which contains N integers p_i1 p_i2 ... p_iN, where pij is the j-th element of the i-th permutation.

Then, output K more lines. The i-th of these gives the instructions that you will apply to the i-th array given in the input. Each such line must begin with one integer S', where 0 ≤ S' ≤ S, and must continue with S' integers X₁, X₂, ..., X_S', where 1 ≤ X_k ≤ P' for all k. Here, X_k represents that the k-th instruction you apply to the i-th array is the X_k-th permutation (counting starting from 1) in your list of permutations. These instructions must yield an array with the elements of the i-th input array, sorted in nondecreasing order.

• 1 ≤ T ≤ 10.
• S = 450.
• 1 ≤ K ≤ 30.
• 2 ≤ N ≤ 50.
• 1 ≤ A_ij ≤ 1000, for all i and j.

• P = 20.

• P = 5.

In Sample Case #1, we can define up to P = 20 permutations. One viable strategy uses only these two:

1. 3 1 2
2. 2 1 3

We can handle the four arrays as follows:

• 10 10 11: This is already sorted in nondecreasing order, so we do not need to do anything.
• 17 4 1000: We can apply permutation #2 to yield 4 17 1000.
• 999 998 997: One option is to first apply permutation #2 to turn the array into 998 999 997, then apply permutation #1 to turn the array into 997 998 999.
• 10 10 11: This is the same as the first array. Applying permutation #2 also yields array sorted in nondecreasing order. (But we could have used the line 0 as we did before.)

In Sample Case #2, notice that we can use the same permutation instruction more than once on the same array, if desired.