Submission #1085457

#TimeUsernameProblemLanguageResultExecution timeMemory
1085457guagua0407Sorting (IOI15_sorting)C++17
20 / 100
2 ms604 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; vector<int> p; vector<int> x,y; vector<pair<int,int>> vec; bool check(int mid){ vector<int> pp=p; for(int i=0;i<mid;i++){ swap(pp[x[i]],pp[y[i]]); } vector<bool> vis(n); vec.clear(); for(int i=0;i<n;i++){ if(vis[i]) continue; int cur=i; while(!vis[cur]){ vis[cur]=true; cur=pp[cur]; if(cur!=i){ vec.push_back({i,cur}); } } } if((int)vec.size()<=mid) return true; else return false; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; m=M; p.resize(n); x.resize(m); y.resize(m); for(int i=0;i<n;i++){ p[i]=S[i]; } for(int i=0;i<m;i++){ x[i]=X[i]; y[i]=Y[i]; P[i]=0; Q[i]=0; } int l=0,r=m; while(l<r){ int mid=(l+r)/2; if(check(mid)){ r=mid; } else{ l=mid+1; } } check(l); vector<int> pp=p; set<int> SS; for(int i=0;i<n;i++){ if(pp[i]!=i){ SS.insert(i); } } for(int i=0;i<l;i++){ if(pp[x[i]]!=x[i]) SS.erase(x[i]); if(pp[y[i]]!=y[i]) SS.erase(y[i]); swap(pp[x[i]],pp[y[i]]); if(pp[x[i]]!=x[i]) SS.insert(x[i]); if(pp[y[i]]!=y[i]) SS.insert(y[i]); if(!SS.empty()){ int a=*SS.begin(); int b=pp[a]; P[i]=a; Q[i]=b; if(pp[a]!=a) SS.erase(a); if(pp[b]!=b) SS.erase(b); swap(pp[a],pp[b]); if(pp[a]!=a) SS.insert(a); if(pp[b]!=b) SS.insert(b); } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...