Submission #155927

#TimeUsernameProblemLanguageResultExecution timeMemory
155927junodeveloperSorting (IOI15_sorting)C++14
100 / 100
508 ms22904 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; int n,m,*x,*y,*s,*p,*q; int a[500010],b[500010],c[500010],d[500010]; bool f(int z) { int i,j; for(i=0;i<n;i++) { a[i]=b[i]=s[i]; } for(i=0;i<z;i++) { swap(a[x[i]],a[y[i]]); } for(i=0;i<n;i++) { c[a[i]]=i; d[b[i]]=i; } j=0; for(i=0;i<z;i++) { swap(d[b[x[i]]],d[b[y[i]]]); swap(b[x[i]],b[y[i]]); while(j<n&&a[j]==j)j++; if(j==n)p[i]=q[i]=0; else { p[i]=d[j],q[i]=d[a[j]]; swap(b[d[j]],b[d[a[j]]]); swap(d[j],d[a[j]]); c[a[j]]=c[j]; swap(a[j],a[c[j]]); c[j]=j; } } for(i=0;i+1<n;i++) if(a[i]>a[i+1]) return false; return true; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N;s=S;m=M;x=X;y=Y;p=P;q=Q; int lo=0,hi=M; while(lo<hi) { int mid=(lo+hi)/2; if(f(mid))hi=mid; else lo=mid+1; } f(lo); return lo; }
#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...