#PU1472. USACO 2025 January Contest, Silver — Problem 3. Table Recovery

USACO 2025 January Contest, Silver — Problem 3. Table Recovery

USACO 2025 January Contest, Silver — Problem 3. Table Recovery

题目描述

Bessie has an N×NN\times N (1≤N≤10001\le N\le 1000) addition table where the integer in the cell at row rr and column cc is r+cr+c, for all 1≤r,c≤N1\le r,c\le N. For example, for N=3N=3, the table would look like this: 2 3 4 3 4 5 4 5 6 Unfortunately, Elsie got ahold of the table and permuted it by performing the following three types of operations as many times as she wanted. Swap two rows Swap two columns Select two values aa and bb that are both present in the table, then simultaneously change every occurrence of aa to bb and every occurrence of bb to aa. Elsie will always perform operations in increasing order of type; that is, she performs as many operations as she likes (possibly none) first of type 11, then of type 22, and finally of type 33. Help Bessie recover a possible state of the table after Elsie finished applying all of her operations of types 11 and 22, but before applying any operations of type 33. There may be multiple possible answers, in which case you should

输入格式

The first line contains NN. The next NN lines each contain NN integers, representing Bessie's addition table after Elsie has permuted it.

输出格式

The lexicographically minimum possible state of the table after all operations of types 1 and 2, but before any operations of type 3. It is guaranteed that the answer exists.

数据范围

Inputs 4-5: N≤6N\le 6 Inputs 6-7: N≤8N\le 8 Inputs 8-11: N≤100N\le 100 Inputs 12-15: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

1
2
2
Regardless of what operations Elsie performs, the table won't change.

样例 2

3
3 4 2
5 2 3
6 3 5
4 2 3
5 3 4
6 4 5
Here is a possible sequence of operations Elsie might have performed.
2 3 4
3 4 5
4 5 6
-> (op 1: swap columns 2 and 3)
2 4 3
3 5 4
4 6 5
-> (op 1: swap columns 1 and 2)
4 2 3
5 3 4
6 4 5
-> (op 3: swap values 2 and 3)
4 3 2
5 2 4
6 4 5
-> (op 3: swap values 3 and 4)
3 4 2
5 2 3
6 3 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
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

提示

types 1 and 2, but it is not the lexicographically smallest because the second entry of the first row is larger than in the correct answer. 4 6 5 3 5 4 2 4 3