Maximize Mismatch

upobir BRACU জয়যাত্রা’50 Techfe...
Limits 1s, 512 MB · Custom Checker

You are given a permutation $P$ of number $1, \cdots , n$ (I.E. each number occurs exactly once). Now you want to introduce some chaos to this permutation. To introduce chaos, you can perform at most $k$ swaps between adjacent positions. The chaosness of the final permutation is calculated as the count of the mismatches I.E. the number of indices $i$ such that $P[i] \neq i$ (the indices are 1-indexed). Output the maximum number of mismatch you can make and also output such a sequence of swaps.


There will be $T$ testcases.

Each testcase begins with a line containing space separated numbers $n$, $k$. Next line contains $n$ space separated numbers representing the initial permutation.

$1 \leq T \leq 10^5$
$3 \leq n \leq 10^5$
$0 \leq k \leq n$
sum of $n$ over all testcases $ \leq 10^5 $


For each testcase first output one number $s$ in a line, $s$ is the number of swaps you will perform. In the next $s$ lines, output the swaps to be performed. To swap positions $x$ and $y$ output the numbers $x$ and $y$. Note that the swaps you perform should be between adjacent positions.

In case of multiple answer, you can output any.


4 2
1 4 2 3
10 2
1 2 3 4 5 6 7 8 9 10
1 2
1 2
9 10


Login to submit.


95% Solution Ratio
MursaleenEarliest, Apr '21
steinumFastest, 0.0s
steinumLightest, 5.5 kB
steinumShortest, 780B
Toph uses cookies. By continuing you agree to our Cookie Policy.