/ 
Time Limit: 2 sec / Memory Limit: 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.