Switch and Flip (Codeforces 1491G)
Tags: Math, graphs

There are $$$n$$$ coins labeled from $$$1$$$ to $$$n$$$. Initially, coin $$$c_i$$$ is on position $$$i$$$ and is facing upwards (($$$c_1, c_2, \dots, c_n)$$$ is a permutation of numbers from $$$1$$$ to $$$n$$$). You can do some operations on these coins. In one operation, you can do the following:Choose $$$2$$$ distinct indices $$$i$$$ and $$$j$$$.Then, swap the coins on positions $$$i$$$ and $$$j$$$.Then, flip both coins on positions $$$i$$$ and $$$j$$$. (If they are initially faced up, they will be faced down after the operation and vice versa)Construct a sequence of at most $$$n+1$$$ operations such that after performing all these operations the coin $$$i$$$ will be on position $$$i$$$ at the end, facing up.Note that you do not need to minimize the number of operations.

Input: The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of coins.The second line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n$$$ ($$$1 \le c_i \le n$$$, $$$c_i \neq c_j$$$ for $$$i\neq j$$$).

Output: In the first line, output an integer $$$q$$$ $$$(0 \leq q \leq n+1)$$$ — the number of operations you used.In the following $$$q$$$ lines, output two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n, i \ne j)$$$ — the positions you chose for the current operation.

Note: Let coin $$$i$$$ facing upwards be denoted as $$$i$$$ and coin $$$i$$$ facing downwards be denoted as $$$-i$$$.The series of moves performed in the first sample changes the coins as such:  $$$[~~~2,~~~1,~~~3]$$$  $$$[-3,~~~1,-2]$$$  $$$[-3,~~~2,-1]$$$  $$$[~~~1,~~~2,~~~3]$$$ In the second sample, the coins are already in their correct positions so there is no need to swap.

Sample Inputs:
3
2 1 3

5
1 2 3 4 5

Sample Outputs:
3
1 3
3 2
3 1

0

Solution (Python):
""""""
import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
    return int(input())

def getStrs():
    return input().split()

def getInts():
    return list(map(int, input().split()))

def getStr():
    return input()

def listStr():
    return list(input())

def getMat(n):
    return [getInts() for _ in range(n)]

def isInt(s):
    return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7
''

def solve():
    N = getInt()
    A = [0] + getInts()
    used = [False] * (N + 1)
    ans = []
    prev_ = -1

    def swap_(i, j):
        ans.append((i, j))
        (A[i], A[j]) = (-A[j], -A[i])
        return
    ''

    def join_cycles(i, j):
        swap_(i, j)
        idx = i
        while A[-A[idx]] > 0:
            swap_(idx, -A[idx])
        idx = -A[idx]
        while A[-A[idx]] > 0:
            swap_(idx, -A[idx])
        swap_(idx, -A[idx])
    for i in range(1, N + 1):
        if A[i] == i:
            used[i] = True
        if used[i]:
            continue
        idx = i
        while True:
            used[idx] = True
            idx = A[idx]
            if idx == i:
                break
        if prev_ == -1:
            prev_ = i
        else:
            join_cycles(prev_, i)
            prev_ = -1
    if prev_ > -1:
        j = 1
        while j <= N and A[j] != j:
            j += 1
        if j <= N:
            join_cycles(prev_, j)
        else:
            (i0, i1) = (prev_, A[prev_])
            swap_(i0, i1)
            j = 1
            while j in [i0, i1]:
                j += 1
            join_cycles(i1, j)
    print(len(ans))
    for (a, b) in ans:
        print(a, b)
    return
solve()

Solution (Python):
n = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
check = p[:]
out = []

def swap(a, b):
    out.append(str(a + 1) + ' ' + str(b + 1))
    (check[a], check[b]) = (-check[b], -check[a])
vis = [False] * n
head = []
for i in range(n):
    if not vis[i]:
        head.append(i)
        vis[i] = True
        curr = i
        while p[curr] != i:
            curr = p[curr]
            vis[curr] = True
while len(head) >= 2:
    a = head.pop()
    b = head.pop()
    swap(a, b)
    curra = p[a]
    while curra != a:
        swap(b, curra)
        curra = p[curra]
    currb = p[b]
    while currb != b:
        swap(a, currb)
        currb = p[currb]
    swap(a, b)
if len(head) == 1:
    a = head[0]
    if p[a] == a:
        pass
    elif p[p[a]] == a:
        a1 = a
        a2 = p[a]
        a3 = b
        swap(a2, a3)
        swap(a1, a3)
        swap(a2, a3)
    else:
        l = [a, p[a]]
        while p[l[-1]] != a:
            l.append(p[l[-1]])
        k = len(l)
        swap(l[0], l[1])
        for i in range(2, k - 1):
            swap(l[0], l[i])
        swap(l[1], l[k - 1])
        swap(l[0], l[k - 1])
        swap(l[0], l[1])
assert check == list(range(n))
assert len(out) <= n + 1
print(len(out))
print('\n'.join(out))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
A = [0] + list(map(int, input().split()))
seen = [0] * (n + 1)
cycles = []
ans = []
for i in range(1, n + 1):
    cur = []
    j = i
    while not seen[j]:
        cur.append(j)
        seen[j] = 1
        j = A[j]
    if len(cur) > 1:
        cycles.append(cur)
for i in range(1, len(cycles), 2):
    (X, Y) = (cycles[i - 1], cycles[i])
    ans.append((X[0], Y[0]))
    for x in X[1:]:
        ans.append((x, Y[0]))
    for y in Y[1:]:
        ans.append((y, X[0]))
    ans.append((X[0], Y[0]))
if len(cycles) % 2:
    X = cycles[-1]
    if len(X) > 2:
        for x in X[:-2]:
            ans.append((x, X[-1]))
        ans.append((X[0], X[-2]))
        ans.append((X[-2], X[-1]))
        ans.append((X[0], X[-1]))
    else:
        Y = []
        for i in range(1, n + 1):
            if i != X[0] and i != X[1]:
                break
        ans.append((i, X[0]))
        ans.append((i, X[1]))
        ans.append((i, X[0]))
print(len(ans))
for a in ans:
    print(*a)