[NICA #1] 交换

Luogu

IDLGB3802

Time1000ms

Memory128MB

DifficultyP3

数学

给定长度为 $n$ 的排列 $a$。排列的含义是，数字 $1,2,3,\cdots n$ 在 $a$ 中**恰好**出现了一次。现在有 $m$ 次操作， - 第 $1$ 次操作将会交换第 $1$ 大（即最大）的元素和第 $2$ 大的元素。 - 第 $2$ 次操作将会交换第 $2$ 大的元素和第 $3$ 大的元素。 - 第 $3$ 次操作将会交换第 $3$ 大的元素和第 $4$ 大的元素。 - …… - 第 $n-1$ 次操作将会交换第 $n-1$ 大的元素和第 $n$ 大的元素。 - 第 $n$ 次操作将会交换第 $1$ 大的元素和第 $2$ 大的元素。 - 第 $n+1$ 次操作将会交换第 $2$ 大的元素和第 $3$ 大的元素。 - 第 $n+2$ 次操作将会交换第 $3$ 大的元素和第 $4$ 大的元素。 - …… - 第 $2n-2$ 次操作将会交换第 $n-1$ 大的元素和第 $n$ 大的元素。 - …… 形式化地讲，第 $i$ 次操作将会交换第 $(i-1)\bmod (n-1)+1$ 大和第 $(i-1)\bmod (n-1)+2$ 大的数字。你需要求出排列最后的情况。 ## Input 第一行有两个整数 $n,m$，含义如题面所示。第二行有 $n$ 个整数 $a_1,a_2,\cdots,a_n$，描述初始时的序列 $a$。 ## Output 输出共一行 $n$ 个整数，表示最终的 $a$ 序列。 [samples] ## Note ### 样例 1 解释 - 初始时：$[1,5,3,4,2]$； - 交换第 $1$ 大和第 $2$ 大：$[1,4,3,5,2]$； - 交换第 $2$ 大和第 $3$ 大：$[1,3,4,5,2]$； - 交换第 $3$ 大和第 $4$ 大：$[1,2,4,5,3]$； - 交换第 $4$ 大和第 $5$ 大：$[2,1,4,5,3]$； - 交换第 $1$ 大和第 $2$ 大：$[2,1,5,4,3]$； - 交换第 $2$ 大和第 $3$ 大：$[2,1,5,3,4]$； - 交换第 $3$ 大和第 $4$ 大：$[3,1,5,2,4]$； - 交换第 $4$ 大和第 $5$ 大：$[3,2,5,1,4]$； - 交换第 $1$ 大和第 $2$ 大：$[3,2,4,1,5]$； - 交换第 $2$ 大和第 $3$ 大：$[4,2,3,1,5]$。 ### 数据范围及约定对于全部数据，保证 $1\le n\le 10^5$，$0\le m\le 10^{1000000}$。

Samples

Input #1

5 10
1 5 3 4 2

Output #1

4 2 3 1 5

Input #2

10 1000000000
4 2 7 6 9 5 3 8 1 10

Output #2

5 3 8 7 9 6 4 10 2 1

Input #3

10 100000000000000000000000000000000000000000000000000
10 9 8 7 6 5 4 3 2 1

Output #3

1 9 10 8 7 6 5 4 3 2

API Response (JSON)

{
  "problem": {
    "name": "[NICA #1] 交换",
    "description": {
      "content": "给定长度为 $n$ 的排列 $a$。排列的含义是，数字 $1,2,3,\\cdots n$ 在 $a$ 中**恰好**出现了一次。现在有 $m$ 次操作， - 第 $1$ 次操作将会交换第 $1$ 大（即最大）的元素和第 $2$ 大的元素。 - 第 $2$ 次操作将会交换第 $2$ 大的元素和第 $3$ 大的元素。 - 第 $3$ 次操作将会交换第 $3$ 大的元素和第 $4$ 大的元素。 - …",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3802"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定长度为 $n$ 的排列 $a$。排列的含义是，数字 $1,2,3,\\cdots n$ 在 $a$ 中**恰好**出现了一次。现在有 $m$ 次操作，\n\n- 第 $1$ 次操作将会交换第 $1$ 大（即最大）的元素和第 $2$ 大的元素。\n- 第 $2$ 次操作将会交换第 $2$ 大的元素和第 $3$ 大的元素。\n- 第 $3$ 次操作将会交换第 $3$ 大的元素和第 $4$ 大的元素。\n- …...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments