제출 #131710

#제출 시각아이디문제언어결과실행 시간메모리
131710nxteru정렬하기 (IOI15_sorting)C++14
0 / 100
3 ms760 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; int n,m,s[200005],x[200005],y[200005],t[200005],a[200005]; bool vis[200005]; bool check(int p){ for(int i=0;i<n;i++)t[i]=s[i]; for(int i=0;i<p;i++)swap(t[x[i]],t[y[i]]); int cnt=n; for(int i=0;i<n;i++)vis[i]=false; for(int i=0;i<n;i++){ int v=i; if(!vis[i])cnt--; while(!vis[v]){ vis[v]=true; v=t[v]; } } return cnt<=p; } 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++)s[i]=S[i]; for(int i=0;i<m;i++)x[i]=X[i],y[i]=Y[i]; int l=0,r=n; while(r-l>1){ int o=(l+r)/2; if(check(o))r=o; else l=o; } for(int i=0;i<n;i++)t[i]=s[i]; for(int i=0;i<r;i++)swap(t[x[i]],t[y[i]]); for(int i=0;i<n;i++)vis[i]=false; int c=0; for(int i=0;i<n;i++){ int v=i; while(!vis[v]){ vis[v]=true; if(vis[t[v]])break; p[c]=v; q[c]=t[v]; c++; v=t[v]; } } for(int i=0;i<n;i++)t[i]=s[i],a[s[i]]=i; for(int i=0;i<c;i++){ swap(t[x[i]],t[y[i]]); a[t[x[i]]]=x[i]; a[t[y[i]]]=y[i]; p[i]=a[p[i]]; q[i]=a[q[i]]; swap(t[p[i]],t[q[i]]); a[t[p[i]]]=p[i]; a[t[q[i]]]=q[i]; } if(c<r)p[c]=0,q[c]=0; 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...