#include "sorting.h"
#include <bits/stdc++.h>
//int N, *S, M, *X, *Y, *P, *Q;
int *A, *D, *ID; //actual, dest, in a
std::deque<int> d;
void do_swap(int i, int j) {
std::swap(D[i], D[j]);
std::swap(A[i], A[j]);
std::swap(ID[i], ID[j]);
d.push_front(i);
d.push_front(j);
}
inline bool check(int mid, int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if (D == NULL)
D = (int*)(malloc(sizeof(int) * N));
if (A == NULL)
A = (int*)(malloc(sizeof(int) * N));
if (ID == NULL)
ID = (int*)(malloc(sizeof(int) * N));
for (int i = 0; i < N; ++i) {
A[i] = S[i];
D[i] = i;
}
for (int i = mid-1; i >= 0; --i)
std::swap(D[X[i]], D[Y[i]]);
for (int i = 0; i < N; ++i) {
ID[D[i]] = i;
}
for (int i = 0; i < N; ++i)
d.emplace_back(i);
for (int i = 0; i < mid; ++i) {
do_swap(X[i], Y[i]);
bool f = false;
while (!d.empty()) {
int k = d.front();
d.pop_front();
if (A[k] != D[k]) { //trzeba swapnac
do_swap(k, ID[k]);
f = true;
break;
}
}
if (!f)
P[i] = Q[i] = 0;
}
for (int i = 0; i < N; ++i)
if (D[i] != i)
return false;
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int lo = 0, hi = M;
while (lo < hi) {
int mid = (lo+hi)/2;
if (check(mid, N, S, M, X, Y, P, Q))
hi = mid;
else
lo = mid+1;
}
check(lo, N, S, M, X, Y, P, Q);
return lo;
}
