DMOPC '22 Contest 4 P6 - K-Sort

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Kurumi just found a particularly nasty cipher on the internet and she needs your help!

The cipher takes the shape of a permutation P of length N. According to information she got from the dark web, the solution to the cipher revolves around what is known as a K-insert.

Specifically, a K-insert of the integer x is a two step process:

  • Step 1: the integer x is removed from P.
  • Step 2: the integer x is inserted after the K-th element in the modified P. In particular, if K = 0, it is inserted at the beginning.

A solution A to the cipher is a sequence of K-inserts that turns P into the identity permutation. In particular, a K-insert of the integer A_i is performed as the i-th action.

In the interest of time, Kurumi wants to know the shortest possible solution. Can you help Kurumi find the shortest possible A? To ensure the integrity of your solution, there may be up to T test cases.


1 \le T \le 10^6

1 \le N \le 10^6

0 \le K \le N - 1

The array P forms a permutation of the integers 1, \ldots, N.

The sum of N over all test cases does not exceed 10^6.

Subtask 1 [10%]

K = 0

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains an integer T, the number of test cases. The remaining 2T lines describe the test cases.

The first line of each test case contains 2 integers, N and K.

The second line of each test case contains N space-separated integers, representing the permutation P.

Output Specification

For each test case, output two lines.

On the first line, output a single integer M, representing the length of A.

On the second line, output M space-separated integers, representing the solution A.

If there are multiple possible solutions, output any one of them.

This problem is graded with a standard checker, so if M = 0, you may output an empty line, no line, or a line containing just whitespace.


For each case within a test, if your output is ill-formatted or your sequence A is not a solution, you will receive 0\% of the points for that case.

Otherwise, let M' be the length of the shortest solution.

  • If M' < M \leq 2M', you will receive 50\% of the points for that case.
  • If M' = M, you will receive 100\% of the points for that case.

Your score for a case will be the minimum of the scores of all the tests in the case. Your score for a batch is the minimum of the scores of all of the tests in the batch.

Sample Input

4 1
2 3 4 1

Sample Output

1 2

Explanation for Sample

After the first K-insert, the permutation becomes [2, 1, 3, 4].

After the second K-insert, the permutation becomes [1, 2, 3, 4].

It can be proven that a solution of shorter length does not exist, so this solution would receive 100\% of the points for this case.


There are no comments at the moment.