#include "sorting.h" #include<bits/stdc++.h> using namespace std; #define maxn 200005 int a[maxn], pos[maxn]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int i,x,l,r,mid,cnt; int ans; l = -1; r = M-1; while(l<=r) { mid = (l+r)/2; // printf("MID = %d\n",mid); //Init for(i=0;i<N;i++) a[i] = S[i]; for(i=0;i<=mid;i++) swap(a[X[i]], a[Y[i]]); for(i=0;i<N;i++) pos[a[i]] = i; //Count cnt = 0; for(i=0;i<N;i++) { x = pos[i]; if(i!=x) { pos[a[i]] = x; // printf("------ swap %d %d\n",i,x); swap(a[i], a[x]); cnt++; } } //Check if(cnt<=mid+1) { ans = mid; r = mid-1; } else l = mid+1; } //Init for(i=0;i<N;i++) a[i] = S[i]; for(i=0;i<=ans;i++) swap(a[X[i]], a[Y[i]]); for(i=0;i<N;i++) pos[a[i]] = i; //Count cnt = 0; for(i=0;i<N;i++) { x = pos[i]; if(i!=x) { pos[a[i]] = x; // printf("------ swap %d %d\n",i,x); swap(a[i], a[x]); P[cnt] = i; Q[cnt] = x; cnt++; } } while(cnt<=ans) P[cnt] = Q[cnt] = 0, cnt++; return ans+1; }