Crazy Diamond (Codeforces 1148C)
Tags: Others, sortings

You are given a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$, where $$$n$$$ is an even number. Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type:   take two indices $$$i$$$ and $$$j$$$ such that $$$2 \cdot |i - j| \geq n$$$ and swap $$$p_i$$$ and $$$p_j$$$. There is no need to minimize the number of operations, however you should use no more than $$$5 \cdot n$$$ operations. One can show that it is always possible to do that.

Input: The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n$$$ is even) — the length of the permutation. The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the given permutation.

Output: On the first line print $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$) — the number of swaps to perform.Each of the following $$$m$$$ lines should contain integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$|a_i - b_i| \ge \frac{n}{2}$$$) — the indices that should be swapped in the corresponding swap.Note that there is no need to minimize the number of operations. We can show that an answer always exists.

Note: In the first example, when one swap elements on positions $$$1$$$ and $$$2$$$, the array becomes sorted.In the second example, pay attention that there is no need to minimize number of swaps.In the third example, after swapping elements on positions $$$1$$$ and $$$5$$$ the array becomes: $$$[4, 5, 3, 1, 2, 6]$$$. After swapping elements on positions $$$2$$$ and $$$5$$$ the array becomes $$$[4, 2, 3, 1, 5, 6]$$$ and finally after swapping elements on positions $$$1$$$ and $$$4$$$ the array becomes sorted: $$$[1, 2, 3, 4, 5, 6]$$$.

Sample Inputs:
2
2 1

4
3 4 1 2

6
2 5 3 1 4 6

Sample Outputs:
1
1 2

4
1 4
1 4
1 3
2 4

3
1 5
2 5
1 4

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LLI():
    return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
    return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
    return [float(x) for x in sys.stdin.readline().split()]

def LS():
    return sys.stdin.readline().split()

def I():
    return int(sys.stdin.readline())

def F():
    return float(sys.stdin.readline())

def S():
    return input()

def pf(s):
    return print(s, flush=True)

def pe(s):
    return print(str(s), file=sys.stderr)

def main():
    n = I()
    a = LI_()
    d = {}
    for i in range(n):
        d[a[i]] = i
    r = []

    def sw(t, u):
        c = a[t]
        e = a[u]
        d[c] = u
        d[e] = t
        a[t] = e
        a[u] = c
        r.append('{} {}'.format(t + 1, u + 1))
    n2 = n // 2
    for i in range(1, n - 1):
        if a[i] == i:
            continue
        t = d[i]
        u = a[i]
        if abs(t - i) < n2:
            p = 0
            if abs(t - p) < n2:
                p = n - 1
            sw(t, p)
            if abs(p - i) < n2:
                p = n - 1 - p
                sw(0, n - 1)
            sw(i, p)
        else:
            sw(t, i)
    if a[0] != 0:
        sw(0, n - 1)
    return '{}\n{}'.format(len(r), '\n'.join(r))
print(main())

Solution (Python):
n = int(input())
n2 = n // 2
p = list(map(int, input().split()))
d = [0] * n
for (i, v) in enumerate(p):
    d[v - 1] = i
r = []

def sw(i, j):
    r.append((i + 1, j + 1))

def swap(i, j):
    if i == j:
        pass
    elif abs(i - j) >= n2:
        sw(i, j)
        p[j] = p[i]
    else:
        ti = n - 1 if i < n2 else 0
        tj = n - 1 if j < n2 else 0
        sw(i, ti)
        if ti != tj:
            sw(ti, tj)
        sw(tj, j)
        if ti != tj:
            sw(ti, tj)
        sw(i, ti)
        p[j] = p[i]
for (i, v) in enumerate(p):
    j = d[i]
    swap(i, j)
    d[v - 1] = j
print(len(r))
print('\n'.join((f'{a} {b}' for (a, b) in r)))

Solution (Python):
n = int(input())
p = list(map(int, input().split()))
index = [None] * (n + 1)
for i in range(n):
    index[p[i]] = i
ret = []
for i in range(n):
    if p[i] == i + 1:
        continue
    target = index[i + 1]
    if abs(i - target) * 2 >= n:
        ret.append((i + 1, target + 1))
    elif i * 2 < n and target * 2 < n:
        ret.extend([(target + 1, n), (i + 1, n), (target + 1, n)])
    elif i * 2 >= n and target * 2 >= 2:
        ret.extend([(target + 1, 1), (i + 1, 1), (target + 1, 1)])
    elif target * 2 < n:
        ret.extend([(n, target + 1), (1, n), (i + 1, 1), (n, 1), (n, target + 1)])
    else:
        ret.extend([(1, target + 1), (1, n), (i + 1, n), (n, 1), (1, target + 1)])
    (p[i], p[target]) = (p[target], p[i])
    index[p[i]] = i
    index[p[target]] = target
print(len(ret))
print('\n'.join(('%d %d' % (swap[0], swap[1]) for swap in ret)))