1148C - Crazy Diamond - CodeForces Solution

#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vc vector<char>
#define nline "\n"
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
// multiset
// typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// set
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define M_PI 3.14159265358979323846
const long long int N = 1e9 + 7;

// pascals triangle
// vvll dp(1003, vll(1003, -1));
// int pastri(ll n, ll k)
// {
//     if (n < k)
//         return 0;
//     if (n == k or !k)
//         return 1;
//     if (dp[n][k] != -1)
//         return dp[n][k];

//  -   return dp[n][k] = (pastri(n - 1, k) + pastri(n - 1, k - 1)) % N;
// }

ll fastMOd(ll a, ll b)
{
    ll ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans = (ans * a) % N;
        a = (a * a) % N;
        b = b >> 1;
    }
    return ans;
}

bool isprime(ll n)
{
    if (n <= 1)
        return false;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

ll my_sqrt(ll tt)
{
    ll left = 0, right = 2000000123;
    while (right > left)
    {
        ll mid = (left + right) / 2;

        if (mid * mid > tt)
            right = mid;
        else
            left = mid + 1;
    }
    return left - 1;
}

// vll minp, primes;
void sieve(ll n)
{
    // minp.assign(n + 1, 0);
    // primes.clear();

    // for (ll i = 2; i <= n; i++)
    // {
    //     if (minp[i] == 0)
    //     {
    //         minp[i] = i;
    //         primes.push_back(i);
    //     }

    //     for (auto p : primes)
    //     {
    //         if (i * p > n)
    //         {
    //             break;
    //         }
    //         minp[i * p] = p;
    //         if (p == minp[i])
    //         {
    //             break;
    //         }
    //     }
    // }
}

void solve()
{
    ll n;
    cin >> n;
    vll a(n);
    unordered_map<ll, ll> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        m[a[i]] = i;
    }
    vll b = a;
    sort(all(b));
    vvll ans;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == b[i])
            continue;
        // cout << a[i] << " " << b[i] << nline;
        if (abs(m[b[i]] - i) >= n / 2)
        {
            ll i1 = i, i2 = m[b[i]];
            m[a[i]] = i2;
            m[b[i]] = i1;
            swap(a[i1], a[i2]);
            ans.push_back({i1, i2});
        }
        else
        {
            ll i1 = i, i2 = m[b[i]];
            m[a[i]] = i2;
            m[b[i]] = i1;
            swap(a[i1], a[i2]);
            ll k;
            if (i + 1 > n / 2 && i2 + 1 > n / 2)
            {
                k = 0;
                ans.push_back({k, i1});
                ans.push_back({k, i2});
                ans.push_back({k, i1});
            }
            else if (i + 1 > n / 2 && i2 + 1 <= n / 2)
            {
                ans.push_back({i1, 0});
                ans.push_back({n - 1, 0});
                ans.push_back({n - 1, i2});
                ans.push_back({n - 1, 0});
                ans.push_back({i1, 0});
            }
            else if (i + 1 <= n / 2 && i2 + 1 > n / 2)
            {
                ans.push_back({i1, n - 1});
                ans.push_back({n - 1, 0});
                ans.push_back({0, i2});
                ans.push_back({n - 1, 0});
                ans.push_back({i1, n - 1});
            }
            else
            {
                k = n - 1;
                ans.push_back({k, i1});
                ans.push_back({k, i2});
                ans.push_back({k, i1});
            }
        }
        // for (auto t : a)
        //     cout << t << " ";
        // cout << nline;
    }
    cout << ans.size() << nline;
    for (auto t : ans)
        cout << t[0] + 1 << " " << t[1] + 1 << nline;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}