C - K Swap 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

長さ N の数列 A=(a_1,\ldots,a_N) があります。また、整数 K が与えられます。

あなたは次の操作を 0 回以上何度でも行えます。

  • 1 \leq i \leq N-K を満たす整数 i を選び、a_i と a_{i+K} の値を入れ替える。

A を昇順に並べ替えることが出来るかどうかを判定してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N-1
  • 1 \leq a_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1 \ldots a_N

出力

A を昇順に並び替えることが出来るならば Yes と、出来ないならば No と出力せよ。

入力例 1

5 2
3 4 1 3 4

出力例 1

Yes

次のように操作をすることで A を昇順に並び替えることが出来ます。

  • i=1 とし、a_1 と a_3 の値を入れ替える。数列は (1,4,3,3,4) となる。
  • i=2 とし、a_2 と a_4 の値を入れ替える。数列は (1,3,3,4,4) となる。

入力例 2

5 3
3 4 1 3 4

出力例 2

No

入力例 3

7 5
1 2 3 4 5 5 10

出力例 3

Yes

操作を行う必要が無い場合もあります。

Score : 300 points

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

  • Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N-1
  • 1 \leq a_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
a_1 \ldots a_N

Output

If it is possible to sort A in ascending order, print Yes; otherwise, print No.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

  • Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
  • Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.