P12997 [GCJ 2022 #3] Revenge of GoroSort

**在本问题中，当提到“随机选择”时，均指从所有有效可能性中均匀随机且独立地选择。** Code Jam 的参赛者曾帮助强大的 Goro 对一个整数数组进行排序（无需阅读该问题即可解决本题）。现在，Goro 再次需要你的帮助。他有 $\mathbf{N}$ 个盒子排成一行放在桌子上，从左到右编号为 1 到 $\mathbf{N}$。每个盒子中恰好有一个球。球的编号也是 1 到 $\mathbf{N}$。Goro 希望球 $i$ 最终位于盒子 $i$ 中，即他希望将球按顺序排列。然而，初始状态并非如此。 当 Goro 用他强壮的拳头敲击桌子时，球会弹到空中并落回盒子中。Goro 可以精确控制，使得每个盒子恰好落回一个球。球可能落回原来的盒子，也可能落入其他盒子。 更厉害的是，Goro 还能在每次敲击前为盒子分配颜色。然后，他可以以某种方式敲击桌子，使得从颜色为 $c$ 的盒子中弹出的球总是落入颜色为 $c$ 的盒子中。尽管这种控制力令人印象深刻，但 Goro 无法进一步干预——在每个颜色组内，球的分配是完全随机的。 例如，假设球的初始顺序为 $1, 4, 3, 6, 5, 2$（如上所述）。他可能会选择（不一定最优）将第一个盒子设为红色，第二个和第六个盒子设为绿色，第三到第五个盒子设为蓝色。敲击桌子后： - 第一个盒子中的 1 会落回原盒子，因为这是唯一的红色盒子。 - 第二个和第六个盒子中的 4 和 2 有 $\frac{1}{2}$ 的概率保持原位，也有 $\frac{1}{2}$ 的概率交换位置。 - 第三、四、五个盒子中的 3、6、5 会以 $\frac{1}{6}$ 的概率变为以下任意一种顺序： - $3, 6, 5$ - $3, 5, 6$ - $6, 3, 5$ - $6, 5, 3$ - $5, 3, 6$ - $5, 6, 3$ 因此，例如，敲击后球变为 $1, 2, 3, 5, 6, 4$ 的概率是 $\frac{1}{12}$。如果 Goro 得到这个或其他非排序结果，他需要为下一轮重新分配盒子颜色，直到最终达到排序状态 $1, 2, 3, 4, 5, 6$。Goro 可以在每次敲击前以任意方式分配颜色，不受之前分配的影响。 你能帮助 Goro 实现一种更高效的策略来排序球吗？题目保证球的初始顺序是随机且非排序的。 ### 交互协议 这是一个交互式问题。 最初，你的程序应读取一行，包含三个整数 $T$、$N$、$K$：测试用例的数量、每个测试用例的盒子数量以及所有测试用例允许的总敲击次数。然后，需要处理 $T$ 个测试用例。 每个测试用例开始时，评测机会发送一行 $N$ 个整数，每个整数从 1 到 $N$ 恰好出现一次，且列表是从所有非排序列表中随机选择的。之后，你需要与评测机进行一系列交互。每次交互如下： - 你发送一行 $N$ 个整数 $C_1, C_2, \ldots, C_N$，每个整数在 1 到 $N$ 之间（含）。$C_i$ 表示你将颜色 $C_i$ 分配给盒子 $i$ 用于下一次敲击。你可以选择颜色的数量和编号方式，但必须为每个盒子分配一个颜色。 - 评测机模拟敲击过程（如题目描述）。如果敲击后球已排序： - 如果这是所有测试用例中的第 $K$ 次交互，且不是最后一个测试用例，评测机会发送一行整数 $-1$ 并停止输出。 - 否则，评测机会发送一行整数 1，并立即开始下一个测试用例（如果有）。如果是最后一个测试用例，你的程序必须无错误退出且不再发送任何内容。 - 如果球未排序： - 如果这是所有测试用例中的第 $K$ 次交互，或你提供了无效输入（如整数不足、颜色编号越界），评测机会发送一行整数 $-1$ 并停止输出。 - 否则，评测机会发送一行整数 0，接着另一行 $N$ 个整数（每个 1 到 $N$ 恰好出现一次且非排序），表示球的新顺序（第 $i$ 个整数是落入盒子 $i$ 的球）。然后你需要开始下一次交互。 通常，如果内存超限或程序运行时错误，你将收到相应的判题结果。此外，如果在收到 $-1$ 后程序仍在等待评测机，将因超时被判为 Time Limit Exceeded。注意，你有责任及时退出程序以避免超时错误。 请注意，评测机每次使用相同的随机源，因此在没有其他错误（如超时、内存超限）的情况下，提交完全相同的代码两次将得到相同的结果。

参见交互协议。

参见交互协议。

**样例解释** 注意，样例交互不满足任何测试集的约束，仅用于说明输入输出格式。 **限制** - $\mathbf{T} = 1000$。 - $\mathbf{N} = 100$。 **测试集 1（8 分，可见判题结果）** - $\mathbf{K} = 16500$。 **测试集 2（10 分，可见判题结果）** - $\mathbf{K} = 12500$。 **测试集 3（3 分，可见判题结果）** - $\mathbf{K} = 11500$。 翻译由 DeepSeek V3 完成