C - K Swap

Contest Duration: 2022-06-04(Sat) 12:00 - 2022-06-04(Sat) 13:40 (local time) (100 minutes) Back to Home

C - K Swap Editorial

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 と出力せよ。

入力例 1Copy

Copy

5 2
3 4 1 3 4

出力例 1Copy

Copy

Yes

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

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

入力例 2Copy

Copy

5 3
3 4 1 3 4

出力例 2Copy

Copy

No

入力例 3Copy

Copy

7 5
1 2 3 4 5 5 10

出力例 3Copy

Copy

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 1Copy

Copy

5 2
3 4 1 3 4

Sample Output 1Copy

Copy

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 2Copy

Copy

5 3
3 4 1 3 4

Sample Output 2Copy

Copy

No

Sample Input 3Copy

Copy

7 5
1 2 3 4 5 5 10

Sample Output 3Copy

Copy

Yes

No operations may be needed.