No.3775 Distant Swap
Rapca1256
aogera
p-adic
tomorunnProblem Statement
You are given a positive integer $K$ and a permutation $P=(P_1,P_2,\cdots,P_N)$ of the positive integers not exceeding $N$.
Determine whether it is possible to sort $P$ in ascending order by performing the following operation $0$ or more times.
If it is possible, find the minimum number of operations required, and show one example of a sequence of operations that achieves this minimum.
- Choose integers $i, j$ such that $1 \le i < j \le N, j - i = K$, and swap $P_i$ and $P_j$.
Input
$N\ K$ $P_1\ P_2\ P_3\ \cdots \ P_N$
The input satisfies the following constraints.
- All input values are integers
- $2 \le N \le 1000$
- $1 \le K \le N-1$
- $P$ is a permutation of the positive integers not exceeding $N$
Output
If $P$ cannot be sorted in ascending order by performing the operation $0$ or more times, print -1 on line $1$.
If it can, print the minimum number of operations required, $m$, on line $1$.
In addition, when $1 \le m$, for each $1 \le k \le m$, if the $k$-th operation swaps $P_i$ and $P_j$ ( $i < j$ ), print $i,j$ in this order, separated by a single space, on line $k+1$.
If there are multiple valid sequences of operations, any of them will be accepted.
Also, print a newline at the end.
Sample
Sample 1
Input
5 2 5 4 1 2 3
Output
3 2 4 1 3 3 5
In operation $1$, swapping $P_2,P_4$ makes $P$ equal to $(5,2,1,4,3)$.
In operation $2$, swapping $P_1,P_3$ makes $P$ equal to $(1,2,5,4,3)$.
In operation $3$, swapping $P_3,P_5$ makes $P$ equal to $(1,2,3,4,5)$.
Since $P$ cannot be sorted in ascending order with $2$ or fewer operations, the answer is $3$.
Sample 2
Input
5 2 5 4 1 3 2
Output
-1
No matter how the operations are performed, $P$ cannot be sorted in ascending order.
Sample 3
Input
10 3 1 2 3 4 5 6 7 8 9 10
Output
0
The sequence may already be in ascending order from the start.
Sample 4
Input
10 3 10 2 3 1 5 6 7 8 9 4
Output
4 1 4 7 10 4 7 7 10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。