#include "sorting.h" #include <iostream> #include <vector> #include <set> using namespace std; int x[600005]; int y[600005]; int vec[200005]; int vec2[200005]; int bila[200005]; int fre[200005]; vector<int>ciclu; int n; void dfs(int poz) { if(fre[poz]==1) { return; } fre[poz]=1; ciclu.push_back(poz); dfs(bila[poz]); } int vmax=10000000; set<pair<int,int> >positii[200005]; pair<int,int>getpositions(int timp,int bila1,int bila2) { pair<int,int> r1=*(prev(positii[bila1].upper_bound({timp,vmax}))); pair<int,int> r2=*(prev(positii[bila2].upper_bound({timp,vmax}))); swap(positii[bila1],positii[bila2]); return make_pair(r1.second,r2.second); } vector<pair<int,int> > solutie(int nroper) { vector<pair<int,int>>oper; for(int i=0;i<n;i++) { fre[i]=0; vec2[i]=vec[i]; positii[vec2[i]].insert({0,i}); } for(int i=0;i<nroper;i++) { positii[vec2[x[i]]].insert({i+1,y[i]}); positii[vec2[y[i]]].insert({i+1,x[i]}); swap(vec2[x[i]],vec2[y[i]]); } for(int i=0;i<n;i++) { bila[i]=vec2[i]; } for(int i=0;i<n;i++) { if(fre[i]==0) { ciclu.clear(); dfs(i); for(int j=1;j<ciclu.size();j++) { oper.push_back(getpositions(oper.size()+1,ciclu[j-1],ciclu[j])); //cout<<ciclu[0]<<" "<<ciclu[j]<<'\n'; //oper.push_back({ciclu[0],ciclu[j]}); } } } if(oper.size()<nroper) { oper.push_back({0,0}); } return oper; } int check(int nroper) { for(int i=0;i<n;i++) { fre[i]=0; vec2[i]=vec[i]; } for(int i=0;i<nroper;i++) { swap(vec2[x[i]],vec2[y[i]]); } for(int i=0;i<n;i++) { bila[i]=vec2[i]; } int pasi=0; for(int i=0;i<n;i++) { if(fre[i]==0) { ciclu.clear(); dfs(i); pasi=pasi+ciclu.size()-1; } } if(pasi<=nroper) { return 1; } return 0; } 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++) { vec[i]=S[i]; } for(int i=0; i<M; i++) { x[i]=X[i]; y[i]=Y[i]; } int st=0,dr=M; while(st<=dr) { int mij=(st+dr)/2; if(check(mij)==1) { dr=mij-1; } else { st=mij+1; } } vector<pair<int,int> >rez2=solutie(dr+1); for(int i=0;i<rez2.size();i++) { P[i]=rez2[i].first; Q[i]=rez2[i].second; } return rez2.size(); }