P13124 [GCJ 2019 Finals] Sorting Permutation Unit

你可能听说过 Google 的张量处理单元（Tensor Processing Units），它们被用于构建神经网络。然而，有一个比机器学习更深奥、更重要的研究领域：排序！ 我们正在研发一种名为“排序置换单元”（Sorting Permutation Unit）的特殊芯片，它能非常快速地对整数数组应用置换。形式化地说，置换是对前 $n$ 个正整数的一种排列： $$\mathbf{p}_{1}, \mathbf{p}_{2}, \ldots, \mathbf{p}_{\mathbf{n}}$$ 将其应用于一个包含 $n$ 个整数的数组 $$\mathbf{a}_{1}, \mathbf{a}_{2}, \ldots, \mathbf{a}_{\mathbf{n}}$$ 会得到新的数组 $$\mathbf{a}_{\mathbf{p}_{1}}, \mathbf{a}_{\mathbf{p}_{2}}, \ldots, \mathbf{a}_{\mathbf{p}_{\mathbf{n}}}$$ 例如，将置换 3, 1, 2, 4 应用于数组 99, 234, 45, 800，会得到新数组 45, 99, 234, 800。 然而，硬件中表示置换的代价很高，因此该单元最多只能使用 $\mathbf{P}$ 个不同的置换。我们需要你的帮助，来确定这些置换应该是什么！ 给定 $\mathbf{K}$ 个长度为 $\mathbf{N}$ 的整数数组，你首先需要指定至多 $\mathbf{P}$ 个你选择的置换（每个置换长度为 $\mathbf{N}$）。然后，对于每一个输入数组，你需要给出一组最多包含 $\mathbf{S}$ 条指令的序列（每条指令是你指定的置换之一）。当按顺序对该数组应用这些指令后，最终得到的数组必须是非递减有序的。在每个数组的指令序列中，你可以对每个置换使用零次或多次（不要求连续）。

输入的第一行是测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为四个整数 $\mathbf{P}$、$\mathbf{S}$、$\mathbf{K}$ 和 $\mathbf{N}$，分别表示最多允许的置换数、对每个数组最多允许的指令数、数组的数量以及每个数组中的整数个数。接下来有 $\mathbf{K}$ 行，每行包含 $\mathbf{N}$ 个整数 $\mathbf{A}_{\mathbf{i}1}$、$\mathbf{A}_{\mathbf{i}2}$、...、$\mathbf{A}_{\mathbf{iN}}$，其中第 $i$ 行的第 $j$ 个整数 $\mathbf{A}_{\mathbf{ij}}$ 表示第 $i$ 个数组的第 $j$ 个值。

对于每个测试用例，按以下顺序输出： - 首先输出一行 `Case #x:`，其中 $x$ 是测试用例编号（从 1 开始）。 - 输出一行一个整数 $\mathbf{P}'$，表示你选择使用的置换数量，$1 \leq \mathbf{P}' \leq \mathbf{P}$。 - 接下来输出 $\mathbf{P}'$ 行，每行包含 $\mathbf{N}$ 个整数 $\mathbf{p}_{\mathbf{i}1}$ $\mathbf{p}_{\mathbf{i}2}$ ... $\mathbf{p}_{\mathbf{iN}}$，表示第 $i$ 个置换的内容。 然后，再输出 $\mathbf{K}$ 行。第 $i$ 行表示你将应用于输入中第 $i$ 个数组的指令序列。每行首先是一个整数 $\mathbf{S}'$，$0 \leq \mathbf{S}' \leq \mathbf{S}$，接着是 $\mathbf{S}'$ 个整数 $\mathbf{X}_{1}$、$\mathbf{X}_{2}$、...、$\mathbf{X}_{\mathbf{S}'}$，其中 $1 \leq \mathbf{X}_{\mathbf{k}} \leq \mathbf{P}'$。这里，$\mathbf{X}_{\mathbf{k}}$ 表示对第 $i$ 个数组应用的第 $k$ 条指令是你置换列表中第 $\mathbf{X}_{\mathbf{k}}$ 个置换（从 1 开始编号）。这些指令应用后，得到的数组必须是输入数组元素的非递减排列。

**样例解释** 在样例 1 中，我们最多可以定义 $\mathbf{P} = 20$ 个置换。一种可行的策略只用到了以下两个： 1. 3 1 2 2. 2 1 3 我们可以这样处理四个数组： - 10 10 11：已经是非递减有序，无需操作。 - 17 4 1000：可以应用第 2 个置换，得到 4 17 1000。 - 999 998 997：可以先应用第 2 个置换，得到 998 999 997，再应用第 1 个置换，得到 997 998 999。 - 10 10 11：与第一个数组相同，也可以应用第 2 个置换得到有序数组（当然也可以直接输出 0）。 在样例 2 中，注意同一个置换指令可以在同一个数组上多次使用。 **数据范围** - $1 \leq \mathbf{T} \leq 10$。 - $\mathbf{S} = 450$。 - $1 \leq \mathbf{K} \leq 30$。 - $2 \leq \mathbf{N} \leq 50$。 - $1 \leq \mathbf{A}_{\mathbf{ij}} \leq 1000$，对于所有 $i$ 和 $j$。 **测试点 1（5 分，可见）** - $\mathbf{P} = 20$。 **测试点 2（22 分，隐藏）** - $\mathbf{P} = 5$。 由 ChatGPT 4.1 翻译