#include "sorting.h"
#include <iostream>
#include <vector>
#include <cassert>
int const nmax = 1000000;
int init[1 + nmax], n;
int v[1 + nmax], frec[1 + nmax], f[1 + nmax], pos[1 + nmax];
int xswap[1 + nmax], yswap[1 + nmax];
int pswap[1 + nmax], qswap[1 + nmax];
bool valid(int target){
for(int i = 0; i < n; i++)
v[i] = init[i];
for(int i = 0; i < target; i++) {
std::swap(v[xswap[i]], v[yswap[i]]);
std::swap(v[pswap[i]], v[qswap[i]]);
}
/*
std::cout << '\n';
for(int i = 0; i < target; i++)
std::cout << v[i] << " ";
std::cout << '\n';
*/
for(int i = 0; i < target; i++)
if(v[i] != i)
return false;
return true;
}
bool tryit(int target){
for(int i = 0; i < n; i++)
f[i] = i;
for(int i = target - 1 ; 0 <= i; i--)
std::swap(f[xswap[i]], f[yswap[i]]);
for(int i = 0; i < n; i++)
v[i] = init[i];
for(int i = 0; i < n; i++)
pos[v[i]] = i;
std::vector<int> q;
for(int i = 0; i < n; i++)
if(f[i] != v[i])
q.push_back(i);
for(int i = 0; i < target; i++){
/*
for(int j = 0; j < n; j++)
std::cout << v[j] << " ";
std::cout << '\n';
for(int j = 0; j < n; j++)
std::cout << f[j] << " ";
std::cout << '\n';
for(int j = 0; j < n; j++)
std::cout << pos[j] << " ";
std::cout << '\n';
std::cout << '\n';
*/
std::swap(v[xswap[i]], v[yswap[i]]);
pos[v[xswap[i]]] = xswap[i];
pos[v[yswap[i]]] = yswap[i];
std::swap(f[xswap[i]], f[yswap[i]]);
/*
for(int j = 0; j < n; j++)
std::cout << v[j] << " ";
std::cout << '\n';
for(int j = 0; j < n; j++)
std::cout << f[j] << " ";
std::cout << '\n';
for(int j = 0; j < n; j++)
std::cout << pos[j] << " ";
std::cout << '\n';
std::cout << '\n' << '\n';
*/
while(0 < q.size()){
int e = q.back();
q.pop_back();
//std::cout << "q:" << e << '\n';
if(f[e] == v[e]){
continue;
} else {
pswap[i] = e;
qswap[i] = pos[f[e]];
std::swap(v[pswap[i]], v[qswap[i]]);
pos[v[pswap[i]]] = pswap[i];
pos[v[qswap[i]]] = qswap[i];
// std::cout << "&" << e << " " << pos[f[e]] << '\n';
break;
}
}
}
/*
for(int i = 0; i < n; i++)
std::cout << v[i] << " ";
std::cout << '\n';
*/
while(0 < q.size()){
int e = q.front();
q.pop_back();
if(f[e] == v[e])
continue;
else
return false;
}
//std::cout << "|";
return true;
}
int binarysearch(int from, int to){
if(from < to){
int mid = (from + to) / 2;
if(tryit(mid))
return binarysearch(from, mid);
else
return binarysearch(mid + 1, to);
} else
return from;
}
int findSwapPairs(int N_, int S_[], int M, int X_[], int Y_[], int P[], int Q[]) {
n = N_;
for(int i = 0; i < n; i++)
init[i] = S_[i];
for(int i = 0; i < M; i++)
xswap[i] = X_[i];
for(int i = 0; i < M; i++)
yswap[i] = Y_[i];
//tryit(3);
//int steps = 3;
///*
int steps = binarysearch(0, M);
tryit(steps);
//*/
for(int i = 0; i < steps; i++)
P[i] = pswap[i];
for(int i = 0; i < steps; i++)
Q[i] = qswap[i];
//std::cout << steps << '\n';
if(valid(steps) == 0)
assert(1 < 0);
return steps;
}
