시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB0000.000%

문제

In this problem, when something is said to be chosen at random, it means uniformly at random from among all valid possibilities, and independently of any other choice.

Code Jam contestants once helped the mighty Goro sort an array of integers. (You do not need to read that problem to solve this one.) Once again, Goro needs your help. He has $\mathbf{N}$ boxes lined up on the table in a single row, numbered $1$ through $\mathbf{N}$ from left to right. Each box has exactly one ball inside. Balls are also numbered $1$ through $\mathbf{N}$. Goro wants ball $i$ to end up in box $i$, for all $i$. That is, he wants to leave the balls in sorted order. Unfortunately, that is not initially the case.

When Goro bumps the table with his powerful fists, balls pop up in the air and fall back in boxes. Goro can do this so accurately that exactly one ball falls into each box. A ball may fall into the same box it came out of, or into a different one.

Better yet, Goro also has the ability to assign colors to boxes before each bump. Then, he can bump the table in such a way that balls coming out of a box of color $c$ always fall into a box of color $c$. As impressive as this accuracy is, Goro does not have any more control than that. Within each color, balls end up assigned to boxes at random.

For example, suppose the balls appear in the order $1, 4, 3, 6, 5, 2$ (as seen above). He might choose — not necessarily optimally — to give the first box the color red, the second and sixth boxes the color green, and the third through fifth boxes the color blue. Then, after Goro bumps the table,

  • The $1$ in the first box falls back into the same box, because that is the only red box.
  • The $4$ and $2$ in the second and sixth boxes remain in place with probability $\frac{1}{2}$, and switch places with probability $\frac{1}{2}$.
  • The $3, 6, 5$ in the third, fourth, and fifth boxes end up in one of the following orders, each with probability $\frac{1}{6}$:
    • $3, 6, 5$
    • $3, 5, 6$
    • $6, 3, 5$
    • $6, 5, 3$
    • $5, 3, 6$
    • $5, 6, 3$

So, for example, the probability of the bump leaving the balls in the order $1, 2, 3, 5, 6, 4$ is $\frac{1}{12}$. If Goro got this or some other non-sorted result, he would have to designate a set of box colors for the next round, and so on, until he eventually arrives at the sorted $1, 2, 3, 4, 5, 6$. Goro can assign colors to boxes in any way before each bump, regardless of previous assignments.

Can you help Goro implement a better strategy that will efficiently sort the balls? It is guaranteed that the balls start in a random non-sorted order.

입력과 출력

This is an interactive problem.

Initially, your program should read a single line containing three integers, $\mathbf{T}$ $\mathbf{N}$ $\mathbf{K}$: the number of test cases, the number of boxes per test case, and the total number of bumps allowed for all test cases combined. Then, $\mathbf{T}$ test cases must be processed.

Each test case begins with the judge sending one line with $\mathbf{N}$ integers, with each integer from $1$ to $\mathbf{N}$ appearing exactly once, and with the list chosen at random from all non-sorted lists. Then you must engage in a series of interactions with the judge. Each interaction works as follows:

  • You send one line of $\mathbf{N}$ integers $C_1, C_2, \dots, C_{\mathbf{N}}$, in which each integer is between $1$ and $\mathbf{N}$, inclusive. Each $C_i$ represents that you are assigning color $C_i$ to box $i$ for the next bump. You may choose how many colors there are and how they are numbered, but you must assign a color to each box.
  • The judge simulates the bump as explained in the statement. If this results in the balls being in sorted order:
    • If this interaction was the $\mathbf{K}$-th interaction across all test cases, and this was not the last test case, the judge sends one line with the integer $-1$ and does not output anything further.
    • Otherwise, the judge sends one line with the integer $1$ and then immediately begins the next test case, if there is one. If this was the last test case, your program must exit without error and without sending anything further.
  • Otherwise, the balls are not sorted, and:
    • If this interaction was the $\mathbf{K}$-th across all test cases, or if you provided an invalid line (e.g., too few integers, or color numbers out of range), the judge sends one line with the integer $-1$ and does not output anything further.
    • If this was not your $\mathbf{K}$-th interaction, the judge sends one line with the integer $0$, and then another line with $\mathbf{N}$ integers, with each integer from $1$ to $\mathbf{N}$ appearing exactly once, and in non-sorted order, representing the new order of the balls, that is, the $i$-th of these integers is the ball that fell into box $i$. Then you must begin another interaction.

As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment. Also, if your program continues to wait for the judge after receiving a $-1$, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error.

Be advised that the judge uses the same source of randomness each time, so in the absence of other errors (e.g. Time Limit Exceeded, Memory Limit Exceeded), submitting the exact same code twice will yield the same outcome twice.

제한

  • $\mathbf{T} = 1000$.
  • $\mathbf{N} = 100$.

Test Set 1 (8점)

  • $\mathbf{K} = 16500$.

Test Set 2 (10점)

  • $\mathbf{K} = 12500$.

Test Set 3 (3점)

  • $\mathbf{K} = 11500$.

예제 입력 1

2 4 8
1 4 3 2

0
1 4 3 2

1
2 1 4 3

1

예제 출력 1



1 2 3 2


1 2 3 2


4 4 4 4

힌트

Note that the sample interaction does not satisfy the constraints of any of the test sets. It is only presented to clarify the input and output format.

테스팅 툴

출처

Contest > Google > Code Jam > Google Code Jam 2022 > Round 3 A번

채점 및 기타 정보

  • 예제는 채점하지 않는다.