[语言月赛 202405] 更好的交换

Luogu

IDLGB3977

Time1000ms

Memory512MB

DifficultyP2

2024O2优化数组语言月赛

小 S 有一个奇怪的机关拼图。这个拼图可以看作一个 $n$ 行 $n$ 列的方阵 $A$，第 $i$ 行第 $j$ 列的位置上有一个正整数 $A_{i, j}$。与寻常拼图不同的是，这个机关拼图上的数字不能随意移动，必须按照如下规则**之一**操作： - 选择拼图上的第 $x$ 行和第 $y$ 行，交换这两**行**； - 选择拼图上的第 $x$ 列和第 $y$ 列，交换这两**列**。为了复原这个拼图，小 S 将会操作共 $m$ 次，每次操作格式如下： - `1 x y`，表示交换第 $x$ 行和第 $y$ 行； - `0 x y`，表示交换第 $x$ 列和第 $y$ 列；请你输出复原后的拼图。 ## Input 第一行，两个正整数 $n$ 和 $m$，分别表示拼图的行数、列数和总操作次数。接下来 $n$ 行，每行 $n$ 个正整数 $A_{i, j}$，表示拼图上第 $i$ 行，第 $j$ 列上的数字。接下来 $m$ 行，每行三个正整数 $op, x, y$，其中 $op$ 表示操作类型，$x, y$ 代表被操作的行号或列号。 ## Output 输出共 $n$ 行，每行 $n$ 个正整数，表示复原后的拼图。 [samples] ## Note ### 样例 1 解释第一次操作，交换了第 $2$ 列和第 $3$ 列；第二次操作，没有发生变化。 ### 样例 2 解释第一次操作，交换第 $2$ 行和第 $3$ 行，拼图变为： $$ \begin{aligned} 11 \ 12 \ 13\\ \textcolor{red}{31 \ 32 \ 33}\\ \textcolor{blue}{21 \ 22 \ 23} \end{aligned} $$ 第二次操作，交换第 $2$ 列和第 $3$ 列，拼图变为： $$ \begin{aligned} 11 \ \textcolor{red}{13} \ \textcolor{blue}{12} \\ 31 \ \textcolor{red}{33} \ \textcolor{blue}{32} \\ 21 \ \textcolor{red}{23} \ \textcolor{blue}{22} \end{aligned} $$ ### 数据范围对于前 $30 \%$ 的数据，保证每一行数字相同；对于前 $60 \%$ 的数据，保证 $1 \leq m \leq 3 \times 10^3$。对于 $100 \%$ 的数据，保证 $1 \leq m \leq 10^6, 1 \leq n, A_{i, j} \leq 10^3, 1 \leq x, y \leq n$，$0 \leq op \leq 1$。

Samples

Input #1

Output #1

4 6 5 
3 1 2 
9 7 8

Input #2

Output #2

11 13 12 
31 33 32 
21 23 22

Input #3

4 4               
12 32 42 82
53 43 34 98
90 32 42 53
37 17 88 10
0 2 4
1 2 4
0 1 4
1 1 3

Output #3

32 53 42 90 
17 10 88 37 
32 82 42 12 
43 98 34 53

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202405] 更好的交换",
    "description": {
      "content": "小 S 有一个奇怪的机关拼图。这个拼图可以看作一个 $n$ 行 $n$ 列的方阵 $A$，第 $i$ 行第 $j$ 列的位置上有一个正整数 $A_{i, j}$。 与寻常拼图不同的是，这个机关拼图上的数字不能随意移动，必须按照如下规则**之一**操作： - 选择拼图上的第 $x$ 行和第 $y$ 行，交换这两**行**； - 选择拼图上的第 $x$ 列和第 $y$ 列，交换这两**列**。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3977"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 S 有一个奇怪的机关拼图。这个拼图可以看作一个 $n$ 行 $n$ 列的方阵 $A$，第 $i$ 行第 $j$ 列的位置上有一个正整数 $A_{i, j}$。\n\n与寻常拼图不同的是，这个机关拼图上的数字不能随意移动，必须按照如下规则**之一**操作：\n\n- 选择拼图上的第 $x$ 行和第 $y$ 行，交换这两**行**；\n- 选择拼图上的第 $x$ 列和第 $y$ 列，交换这两**列**。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments