#define debug 0
#include "sorting.h"
#include <bits/stdc++.h>
//int N, *S, M, *X, *Y, *P, *Q;
int n;
int *A, *D, *ID, *IA; //actual, dest, in d, in a
void print_state() {
if (!debug)
return;
std::cerr << "D[i]:\n";
for (int i = 0; i < n; ++i) std::cerr << D[i] << ' ';
std::cerr << "\nID:\n";
for (int i = 0; i < n; ++i) std::cerr << ID[i] << ' ';
std::cerr << "\nA:\n";
for (int i = 0; i < n; ++i) std::cerr << A[i] << ' ';
std::cerr << "\nIA:\n";
for (int i = 0; i < n; ++i) std::cerr << IA[i] << ' ';
std::cerr << '\n';
}
inline bool check(int mid, int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if (debug) std::cerr << "entering check function\n\n\n\n\n\n\n";
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));
if (IA == NULL)
IA = (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;
IA[A[i]] = i;
}
if (debug) {
std::cerr << "this is the initial state of the simulation, mid " << mid << " ";
print_state();
}
int j = 0;
for (int i = 0; i < mid; ++i) {
if (debug)
std::cerr << "forced swap: " << X[i] << ' ' << Y[i] << '\n';
std::swap( A[X[i]], A[Y[i]]);
std::swap(IA[A[X[i]]], IA[A[Y[i]]]);
std::swap( D[X[i]], D[Y[i]]);
std::swap(ID[D[X[i]]], ID[D[Y[i]]]);
if (debug) {
std::cerr << "this is the state after forced swap:\n";
print_state();
}
bool f = false;
while (j < N) {
int k = IA[j++];
if (A[k] != D[k]) {
if (debug) std::cerr << "swapping " << k << ' ' << ID[A[k]] << '\n';
P[i] = k;
Q[i] = ID[A[k]];
std::swap(IA[A[P[i]]], IA[A[Q[i]]]);
std::swap( A[P[i]], A[Q[i]]);
//std::swap(IA[A[k]], IA[A[ID[A[k]]]]);
f = true;
break;
}
}
if (f == false) {
if (debug)
std::cerr << "no swap\n";
P[i] = Q[i] = 0;
}
if (debug) {
std::cerr << "this is the state after my swap:\n";
print_state();
}
}
for (int i = 0; i < N; ++i)
if (A[i] != i)
return false;
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
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;
}
