Submission #127795

#TimeUsernameProblemLanguageResultExecution timeMemory
127795tinjyuGondola (IOI14_gondola)C++14
90 / 100
28 ms4984 KiB
#include "gondola.h" #include <iostream> using namespace std; long long int ans[1000005]; long long int a[1000005],b[1000005],n; int qs(int s,int e) { if(s>=e)return 0; int l=s,r=e,mid=(a[l]+a[r])/2; while(l<=r) { while(a[l]<mid)l++; while(a[r]>mid)r--; if(l<=r) { swap(a[l],a[r]); swap(b[l],b[r]); l++; r--; } } qs(s,r); qs(l,e); } int valid(int N, int a[]) { n=N; int tmp=-1,mi=500005,tag[500005]; for(int i=0;i<=500000;i++)tag[i]=0; for(int i=0;i<n;i++) { if(tag[a[i]]==1)return 0; tag[a[i]]++; } for(int i=0;i<n;i++) if(a[i]<=n && a[i]<mi) { tmp=i; mi=a[i]; } if(tmp==-1)return 1; int p=n-1,i=tmp,t=mi; while(p--) { i++; i%=n; t++; if(a[i]<=n && a[i]!=t)return 0; } return 1; } //---------------------- int replacement(int N, int gondolaSeq[], int replacementSeq[]) { n=N; int t=-1; for(int i=0;i<n;i++)a[i]=gondolaSeq[i]; for(int i=0;i<n;i++) { if(a[i]<=n) { t=i; break; } } if(t==-1)for(int i=0;i<n;i++)b[i]=i+1; else { b[t]=a[t]; int now=a[t],i=t; int p=n-1; while(p--) { i++; i%=n; now=now%n+1; b[i]=now; } } //for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl; qs(0,n-1); //for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl; int ans1=0,x=n+1; for(int i=0;i<n;i++) { while(a[i]!=b[i]) { replacementSeq[ans1]=b[i]; b[i]=x; ans1++; x++; } } return ans1; } //---------------------- int countReplacement(int N, int inputSeq[]) { if(valid(N,inputSeq)==0)return 0; n=N; int t=-1; for(int i=0;i<n;i++)a[i]=inputSeq[i]; for(int i=0;i<n;i++) { if(a[i]<=n) { t=i; break; } } long long int ans1=1,x=n+1,tmp; if(t==-1) { for(int i=0;i<n;i++)b[i]=i+1; ans1=(ans1*n)%1000000009; } else { b[t]=a[t]; long long int now=a[t],i=t; long long int p=n-1; while(p--) { i++; i%=n; now=now%n+1; b[i]=now; } } //for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl; qs(0,n-1); //for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl; for(long long int i=0;i<n;i++) { tmp=0; while(a[i]!=b[i]) { b[i]=x; tmp++; x++; } if(tmp!=0) { ans[0]++; ans[ans[0]]=tmp; } } for(long long int i=1;i<=ans[0];i++) { //cout<<ans[i]<<" "; for(long long int j=1;j<=ans[i]-1;j++)ans1=(ans1*(ans[0]-i+1))%1000000009; } return ans1; }

Compilation message (stderr)

gondola.cpp: In function 'int qs(int, int)':
gondola.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...