「USACO 2025.1 Silver」Table Recovery - 题目

内存限制

512 MiB

时间限制

2000 ms

标准输入输出

题目类型

传统

评测方式

文本比较

上传者 admin

原题 usaco

提交提交记录统计讨论

Bessie 有一个（）的加法表，其中对于所有，第行第列的方格中的整数为。例如，对于，表格如下所示：

2 3 4
3 4 5
4 5 6

不幸的是，Elsie 得到了这张表格，并通过执行若干次以下三种类型的操作对表格进行了变换。

交换两行；
交换两列；
选择两个同时存在于表格中的值和，然后同时将每一个更改为，每一个更改为。

Elsie 总是按类型顺序执行操作；也就是说，她首先执行任意数量（可能为零）的类型操作，然后是类型操作，最后是类型操作。

请帮助 Bessie 恢复 Elsie 在执行完所有类型和操作后，但在执行任意类型操作之前，表格的一种可能状态。可能存在多种可能的答案，在这种情况下你应当输出字典序最小的答案。

按字典序比较两个表格时，比较它们在自然顺序（行间从上到下，行内从左到右）下读取时第一个不同的项。

输入的第一行包含。

以下行每行包含个整数，表示 Elsie 变换后的 Bessie 的加法表。

输出所有类型 1 和 2 操作后，类型 3 操作前，表格的字典序最小可能状态。输入保证答案存在。

输入 #1

1
2

输出 #1

输入 #2

输出 #2

4 2 3
5 3 4
6 4 5

输入 #3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

输出 #3

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

样例解释

样例 #1

无论 Elsie 执行什么操作表格均不会改变。

样例 #2

以下是 Elsie 可能执行的一种操作序列。

2 3 4
3 4 5
4 5 6
-> （操作 2：交换列 2 和 3）
2 4 3
3 5 4
4 6 5
-> （操作 2：交换列 1 和 2）
4 2 3
5 3 4
6 4 5
-> （操作 3：交换值 2 和 3）
4 3 2
5 2 4
6 4 5
-> （操作 3：交换值 3 和 4）
3 4 2
5 2 3
6 3 5

注意：以下也是经过类型 1 和 2 操作后表格的一种可能状态，但它不是字典序最小的，因为第一行的第二项比正确答案中的要大。

4 6 5
3 5 4
2 4 3

子任务

测试点 4-5：。
测试点 6-7：。
测试点 8-11：。
测试点 12-15：没有额外限制。

编辑器加载中 …

或者，上传代码文件

#1654. 「USACO 2025.1 Silver」Table Recovery

题目描述

输入格式

输出格式

样例