Sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;

const int MAXN = 600005;

int n, m, cnt;
int p[2][MAXN], x[MAXN], y[MAXN];
int pos[2][MAXN], kraj[MAXN], org[MAXN];
int solx[MAXN], soly[MAXN];

void genKraj (int br) {
    for (int i=0; i<n; i++) {
        kraj[i] = i;
    }
    for (int i=0; i<br; i++) {
        swap(kraj[x[i]], kraj[y[i]]);
    }
}

void f (int a, int b, int ind) {
    int va = p[ind][a], vb = p[ind][b];
    p[ind][a] = vb; p[ind][b] = va;
    pos[ind][va] = b; pos[ind][vb] = a;
}

bool moze (int br) {
    genKraj(br);
    for (int i=0; i<n; i++) {
        p[0][i] = org[i];
        p[1][i] = i;
        pos[0][p[0][i]] = i;
        pos[1][p[1][i]] = i;
    }
    int t = 0;
    for (int i=0; i<br; i++) {
        f(x[i], y[i], 0); f(x[i], y[i], 1);
        while (t < n && pos[0][t] == pos[1][kraj[t]]) t++;
        if (t == n) {
            solx[i] = soly[i] = 0;
        } else {
            solx[i] = pos[0][t];
            soly[i] = pos[1][kraj[t]];
            f(pos[0][t], pos[1][kraj[t]], 0);
        }
    }
    for (int i=0; i<n; i++) {
        if (p[0][i] != i) return 0;
    }
    return 1;
}

int bs () {
    int low = 0, high = m;
    while (low < high) {
        int mid = (low + high) / 2;
        if (moze(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    moze(low);
    return low;
}

int findSwapPairs (int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N; m = M;
    for (int i=0; i<n; i++) {
        org[i] = S[i];
        if (org[i] == i) cnt++;
    }
    if (cnt == n) return 0;
    for (int i=0; i<m; i++) {
        x[i] = X[i]; y[i] = Y[i];
    }
    cnt = bs();
    for (int i=0; i<cnt; i++) {
        P[i] = solx[i]; Q[i] = soly[i];
    }
    return cnt;
}