Submission #71610

#TimeUsernameProblemLanguageResultExecution timeMemory
71610mr_bananaSorting (IOI15_sorting)C++17
100 / 100
252 ms16376 KiB
#include <bits/stdc++.h> #include "sorting.h" using namespace std; const int MN=2e6+100; int n,a[MN],m,x[MN],y[MN],b[MN]; bool mark[MN]; bool check(int x1){ for(int i=0;i<n;i++){ b[i]=a[i]; mark[i]=0; } for(int i=0;i<x1;i++){ swap(b[x[i]],b[y[i]]); } int cmp=0; for(int i=0;i<n;i++){ if(!mark[i]){ int x2=i; do{ mark[x2]=1; x2=b[x2]; }while(x2!=i); cmp++; } } return (n-cmp)<=x1; } int bs(){ int lo=-1,hi=m; while(hi-lo>1){ int mid=(hi+lo)/2; if(check(mid)){ hi=mid; } else{ lo=mid; } } return hi; } 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++){ a[i]=S[i]; } m=M; for(int i=0;i<m;i++){ x[i]=X[i],y[i]=Y[i]; } int r=bs(); for(int i=0;i<n;i++){ b[i]=a[i]; } for(int i=0;i<r;i++){ swap(b[x[i]],b[y[i]]); } int cnt=0; for(int i=0;i<n;i++){ while(b[i]!=i){ p[cnt]=i; q[cnt]=b[i]; swap(b[i],b[b[i]]); cnt++; } } while(cnt<r){ p[cnt]=0; q[cnt]=0; cnt++; } iota(b,b+n,0); iota(a,a+n,0); for(int i=r-1;i>=0;i--){ p[i]=a[p[i]]; q[i]=a[q[i]]; swap(a[b[x[i]]],a[b[y[i]]]); swap(b[x[i]],b[y[i]]); } return r; }
#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...