#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int howManySwaps(int check, int N, vector<int> S, int* X, int* Y, vector<int> el2ind){
//cout<<"how many "<<check<<endl;
for (int i = 0; i<check; i++){
int tmp = S[X[i]];
S[X[i]]=S[Y[i]];
S[Y[i]]=tmp;
tmp = el2ind[S[Y[i]]];
el2ind[S[Y[i]]]=el2ind[S[X[i]]];
el2ind[S[X[i]]]=tmp;
/*for (int t=0; t<N; t++){
cout<<S[t]<<" ";
}cout<<endl;*/
}
//cout<<"done"<<endl;
int swaps = 0;
/*for (int t=0; t<N; t++){
cout<<S[t]<<" ";
}cout<<endl;*/
for (int i = 0; i<N; i++){
if (S[i]==i){
continue;
}
//swapping S[i] and S[el2ind[i]]
int a = el2ind[S[el2ind[i]]], b = el2ind[S[i]], c=S[i], d=S[el2ind[i]];
int tmp = S[i];
S[i]=i;
S[el2ind[i]]=tmp;
el2ind[c]=a;
el2ind[d]=b;
swaps++;
/*for (int t=0; t<N; t++){
cout<<S[t]<<" ";
}cout<<endl;*/
}
//cout<<swaps<<endl;
return swaps;
}
vector<pair<int,int> > answer;
void pushToAns(int check, int N, vector<int> S, int* X, int* Y, vector<int> el2ind){
//cout<<"how many "<<check<<endl;
for (int i = 0; i<check; i++){
int tmp = S[X[i]];
S[X[i]]=S[Y[i]];
S[Y[i]]=tmp;
tmp = el2ind[S[Y[i]]];
el2ind[S[Y[i]]]=el2ind[S[X[i]]];
el2ind[S[X[i]]]=tmp;
}
int swaps = 0;
/*for (int t=0; t<N; t++){
cout<<S[t]<<" ";
}cout<<endl;*/
for (int i = 0; i<N; i++){
if (S[i]==i){
continue;
}
answer.push_back(make_pair(i,el2ind[i]));
//swapping S[i] and S[el2ind[i]]
int a = el2ind[S[el2ind[i]]], b = el2ind[S[i]], c=S[i], d=S[el2ind[i]];
int tmp = S[i];
S[i]=i;
S[el2ind[i]]=tmp;
el2ind[c]=a;
el2ind[d]=b;
swaps++;
/*for (int t=0; t<N; t++){
cout<<S[t]<<" ";
}cout<<endl;*/
}
//cout<<swaps<<endl;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> seq(S,S+N);
vector<int> el2ind(N,0);
for (int i = 0; i<N; i++){
el2ind[seq[i]]=i;
}
//binary search
int l = 0, r = M;
//find first element with success
int count,mid;
while (l<=r){
//cout<<l<<" "<<r<<endl;
mid = (l+r)/2;
count = howManySwaps(mid,N,seq,X,Y,el2ind);
//cout<<count<<" "<<mid<<endl;
if (count<=mid){
r=mid-1;
} else {
l=mid+1;
}
}
pushToAns(l,N,seq,X,Y,el2ind);
//cout<<"answer"<<endl;
/*for (auto a : answer){
cout<<a.first<<" "<<a.second<<endl;
}*/
if (count<l){
for (int i = count; i<l; i++){
answer.push_back(make_pair(0,0));
}
}
//for (auto a : answer){
// cout<<a.first<<" "<<a.second<<endl;
//}
//cout<<l<<endl;
vector<int> swapmap(N);
for (int i = 0; i<N; i++){
el2ind[i]=i;
swapmap[i]=i;
}
if (l==0){
return 0;
}
P[l-1]=answer[l-1].first;
Q[l-1]=answer[l-1].second;
//cout<<"format"<<endl;
for (auto a = l-2; a>=0; a--){
//X[a], Y[a] swapped
//cout<<X[a+1]<<" "<<Y[a+1]<<endl;
int ia = el2ind[X[a+1]];
int ib = el2ind[Y[a+1]];
//cout<<ia<<" "<<ib<<endl;
int tmp = swapmap[ia];
swapmap[ia]=swapmap[ib];
swapmap[ib]=tmp;
tmp = el2ind[X[a+1]];
el2ind[X[a+1]]=el2ind[Y[a+1]];
el2ind[Y[a+1]]=tmp;
/*for (int t=0; t<N; t++){
cout<<swapmap[t]<<" ";
}cout<<endl;
for (int t=0; t<N; t++){
cout<<el2ind[t]<<" ";
}cout<<endl;*/
P[a]=swapmap[answer[a].first];
Q[a]=swapmap[answer[a].second];
}
return l;
}
