102542: [AtCoder]ABC254 C - K Swap
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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.
Input
题意翻译
## 题目翻译 给出一个长为 $n$ 的数列 $a_1, a_2, \cdots, a_n$。再给一个整数 $k$。 每次可以选一个下标 $i$（$1 \le i \le n - k$），将 $a_i$ 和 $a_{i + k}$ 交换。 问能否通过交换让数列 $a$ 成为升序（任意 $a_i \le a_{i +1}$）？ translate by @[liangbowen](https://www.luogu.com.cn/user/367488)。 ## 输入格式 输入包括两行，第一行有 $2$ 个正整数 $n, k$。 第二行有 $n$ 个正整数 $a_1, a_2, \cdots, a_n$。 ## 输出格式 如果可以通过交换变成升序，输出 $\texttt{Yes}$。不能变成升序，输出 $\texttt{No}$。 ## 数据范围 $2 \le n \le 2 \times 10^5$；$1 \le k \le n - 1$；$1 \le a_i \le 10^9$。Output
分数：$300$分
问题描述
我们有一个长度为$N$的序列$A$：$(a_1,\ldots,a_N)$。此外，你还将得到一个整数$K$。
你可以执行零次或多次以下操作。
- 选择一个整数$i$，满足$1 \leq i \leq N-K$，然后交换$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$的值。$A$现在为$(1,4,3,3,4)$。
- 选择$i=2$，交换$a_2$和$a_4$的值。$A$现在为$(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
可能不需要执行任何操作。