#P12910. [AGC006E] Rotate 3x3

    ID: 12094 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-不变量分析奇偶性分析置换循环分解

[AGC006E] Rotate 3x3

题目描述

有一个纵向 33 格、横向 NN 格的网格。自上而下的第 ii 行,自左而右的第 jj 列的格子记为 (i,j)(i, j)。最初,格子 (i,j)(i, j) 上写着整数 i+3j−3i + 3j - 3。

N=5N=5 时的网格

すぬけ君可以进行若干次如下操作:

  • 选择一个 3×33 \times 3 的正方形区域,将该区域内的整数整体旋转 180∘180^\circ。

操作序列示例(蓝色正方形为操作区域)

すぬけ君的目标是使得格子 (i,j)(i, j) 上写着整数 ai,ja_{i,j}。请判断すぬけ君是否能够达成目标。

输入格式

输入从标准输入读入,格式如下:

NN a1,1a_{1,1} a1,2a_{1,2} …\ldots a1,Na_{1,N} a2,1a_{2,1} a2,2a_{2,2} …\ldots a2,Na_{2,N} a3,1a_{3,1} a3,2a_{3,2} …\ldots a3,Na_{3,N}

输出格式

如果すぬけ君能够达成目标,输出 Yes;否则输出 No。

输入输出样例 #1

输入 #1

5
9 6 15 12 1
8 5 14 11 2
7 4 13 10 3

输出 #1

Yes

输入输出样例 #2

输入 #2

5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

输出 #2

No

输入输出样例 #3

输入 #3

5
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15

输出 #3

Yes

输入输出样例 #4

输入 #4

6
15 10 3 4 9 16
14 11 2 5 8 17
13 12 1 6 7 18

输出 #4

Yes

输入输出样例 #5

输入 #5

7
21 12 1 16 13 6 7
20 11 2 17 14 5 8
19 10 3 18 15 4 9

输出 #5

No

说明/提示

限制

  • 5≤N≤1055 \leq N \leq 10^5
  • 1≤ai,j≤3N1 \leq a_{i,j} \leq 3N
  • 所有 ai,ja_{i,j} 互不相同。

样例解释 1

这是题目描述中的图示例。

样例解释 3

初始状态已经是目标排列。