#include "sorting.h" #include <vector> using namespace std; #define MAX_N 200000 vector<int> x, y, arr, idx; vector<int> v; bool vst[MAX_N+1]; int n, m; int R; int dfs(int x){ if(vst[x]) return 0; vst[x]=true; return dfs(v[x])+1; } bool chk(){ int cnt=0; v.clear(); for(int i=0; i<n; i++){ v.push_back(arr[i]); vst[i]=false; } for(int i=0; i<R; i++){ int tmp=v[x[i]]; v[x[i]]=v[y[i]]; v[y[i]]=tmp; } for(int i=0; i<n; i++){ if(!vst[i] && v[i]!=i){ vst[i]=true; cnt+=dfs(v[i]); } } return (cnt<=R); } void sw(int aa, int bb){ int tmp=idx[v[aa]]; idx[v[aa]]=idx[v[bb]]; idx[v[bb]]=tmp; tmp=v[aa]; v[aa]=v[bb]; v[bb]=tmp; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; m=M; for(int i=0; i<N; i++){ arr.push_back(S[i]); idx.push_back(0); } for(int i=0; i<M; i++){ x.push_back(X[i]); y.push_back(Y[i]); } int s=0, e=M-1; while(s<e){ R=(s+e)/2; if(chk()){ e=R; }else{ s=R+1; } } R=(s+e)/2; v.clear(); int cnt=0; for(int i=0; i<n; i++){ v.push_back(arr[i]); vst[i]=false; } for(int i=0; i<R; i++){ int tmp=v[x[i]]; v[x[i]]=v[y[i]]; v[y[i]]=tmp; } for(int i=0; i<n; i++){ while(v[i]!=i){ P[cnt]=v[i]; Q[cnt]=v[v[i]]; cnt++; int tmp=v[i]; v[i]=v[v[i]]; v[tmp]=tmp; } } v.clear(); for(int i=0; i<n; i++){ v.push_back(arr[i]); idx[v[i]]=i; } while(cnt<R){ P[cnt]=1; Q[cnt]=1; cnt++; } for(int i=0; i<R; i++){ sw(X[i], Y[i]); P[i]=idx[P[i]]; Q[i]=idx[Q[i]]; sw(P[i], Q[i]); } return R; }

sorting.cpp: In function 'int dfs(int)':
sorting.cpp:13:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int dfs(int x){
              ^
sorting.cpp:7:13: note: shadowed declaration is here
 vector<int> x, y, arr, idx;
             ^