310370: CF1823B. Sort with Step
Description
Let's define a permutation of length $n$ as an array $p$ of length $n$, which contains every number from $1$ to $n$ exactly once.
You are given a permutation $p_1, p_2, \dots, p_n$ and a number $k$. You need to sort this permutation in the ascending order. In order to do it, you can repeat the following operation any number of times (possibly, zero):
- pick two elements of the permutation $p_i$ and $p_j$ such that $|i - j| = k$, and swap them.
Unfortunately, some permutations can't be sorted with some fixed numbers $k$. For example, it's impossible to sort $[2, 4, 3, 1]$ with $k = 2$.
That's why, before starting the sorting, you can make at most one preliminary exchange:
- choose any pair $p_i$ and $p_j$ and swap them.
Your task is to:
- check whether is it possible to sort the permutation without any preliminary exchanges,
- if it's not, check, whether is it possible to sort the permutation using exactly one preliminary exchange.
For example, if $k = 2$ and permutation is $[2, 4, 3, 1]$, then you can make a preliminary exchange of $p_1$ and $p_4$, which will produce permutation $[1, 4, 3, 2]$, which is possible to sort with given $k$.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $1 \le k \le n - 1$) — length of the permutation, and a distance between elements that can be swapped.
The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — elements of the permutation $p$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$.
OutputFor each test case print
- 0, if it is possible to sort the permutation without preliminary exchange;
- 1, if it is possible to sort the permutation with one preliminary exchange, but not possible without preliminary exchange;
- -1, if it is not possible to sort the permutation with at most one preliminary exchange.
6 4 1 3 1 2 4 4 2 3 4 1 2 4 2 3 1 4 2 10 3 4 5 9 1 8 6 10 2 3 7 10 3 4 6 9 1 8 5 10 2 3 7 10 3 4 6 9 1 8 5 10 3 2 7Output
0 0 1 0 1 -1Note
In the first test case, there is no need in preliminary exchange, as it is possible to swap $(p_1, p_2)$ and then $(p_2, p_3)$.
In the second test case, there is no need in preliminary exchange, as it is possible to swap $(p_1, p_3)$ and then $(p_2, p_4)$.
In the third test case, you need to apply preliminary exchange to $(p_2, p_3)$. After that the permutation becomes $[3, 4, 1, 2]$ and can be sorted with $k = 2$.
Input
题意翻译
给定一个 $1$ 到 $n$ 的排列 $p$ 和一个正整数 $k$。 你可以对 $p$ 进行若干次操作，每次操作交换 $p_i$ 和 $p_j$，其中 $|i-j|=k$。你的目标是使得 $p$ 变为升序。 除此之外，在开始你的操作之前，你还可以**预先交换**任意两个 $p_i$ 和 $p_j$ 一次。 你的任务是判断： 1. 能否在不用预先交换的情况下，使得 $p$ 变为升序； 2. 如果不能，能否在预先交换一次的情况下，使得 $p$ 变为升序。 #### 输入格式 本题有**多组数据**。第一行输入数据组数 $t$（$1\le t\le10^4$）。 对于每组数据，第一行输入 $n$ 和 $k$，第二行输入 $n$ 个整数，其中第 $i$ 个整数表示 $p_i$。 #### 输出格式 对于每组数据： - 如果满足条件 1 输出一行 `0`； - 如果不满足条件 1 但满足条件 2 输出一行 `1`； - 如果条件 1, 2 都不满足输出一行 `-1`。 #### 数据范围 $1\le t\le10^4$，$2\le n\le2\times10^5$，$1\le k\le n-1$，$1\le p_i\le n$。 每组数据的 $n$ 的总和 $\sum n\le2\times10^5$。Output
给定一个长度为n的排列p和一个数k，要求对这个排列进行升序排序。可以通过重复以下操作任意次数（可能为零）来实现：选择排列中的两个元素pi和pj，使得|i-j|=k，并交换它们。但在开始排序之前，最多可以进行一次预先交换：选择任意一对pi和pj并交换它们。任务是检查是否可以在不进行任何预先交换的情况下对排列进行排序；如果不行，检查是否可以通过恰好进行一次预先交换来对排列进行排序。
输入输出数据格式：
输入：
- 第一行包含测试用例的数量t（1≤t≤10^4）。
- 每个测试用例包含两行：
- 第一行包含两个整数n和k（2≤n≤2×10^5；1≤k≤n-1），分别表示排列的长度和可交换元素之间的距离。
- 第二行包含n个整数p1,p2,…,pn（1≤pi≤n），表示排列p的元素。
- 保证所有测试用例的n之和不超过2×10^5。
输出：
- 对于每个测试用例，打印以下内容之一：
- 0，如果可以在不进行预先交换的情况下对排列进行排序。
- 1，如果可以通过进行一次预先交换来对排列进行排序，但无法在不进行预先交换的情况下排序。
- -1，如果无法在最多进行一次预先交换的情况下对排列进行排序。题目大意： 给定一个长度为n的排列p和一个数k，要求对这个排列进行升序排序。可以通过重复以下操作任意次数（可能为零）来实现：选择排列中的两个元素pi和pj，使得|i-j|=k，并交换它们。但在开始排序之前，最多可以进行一次预先交换：选择任意一对pi和pj并交换它们。任务是检查是否可以在不进行任何预先交换的情况下对排列进行排序；如果不行，检查是否可以通过恰好进行一次预先交换来对排列进行排序。 输入输出数据格式： 输入： - 第一行包含测试用例的数量t（1≤t≤10^4）。 - 每个测试用例包含两行： - 第一行包含两个整数n和k（2≤n≤2×10^5；1≤k≤n-1），分别表示排列的长度和可交换元素之间的距离。 - 第二行包含n个整数p1,p2,…,pn（1≤pi≤n），表示排列p的元素。 - 保证所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，打印以下内容之一： - 0，如果可以在不进行预先交换的情况下对排列进行排序。 - 1，如果可以通过进行一次预先交换来对排列进行排序，但无法在不进行预先交换的情况下排序。 - -1，如果无法在最多进行一次预先交换的情况下对排列进行排序。