Submission #7677

#TimeUsernameProblemLanguageResultExecution timeMemory
7677dohyun0324Gondola (IOI14_gondola)C++98
90 / 100
48 ms10704 KiB
#include "gondola.h" #include<algorithm> #include<map> #include<string.h> using namespace std; map<int,int>visit2; int a[100010],ch[250010],visit[250010]; struct data { int x,y; bool operator<(const data&r)const { return x<r.x; } }arr[250010]; int valid(int n, int inputSeq[]) { int i,k=0; for(i=0;i<n;i++) { if(visit[inputSeq[i]]==1) return 0; visit[inputSeq[i]]=1; if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1; } for(i=1;i<=n;i++) { if(ch[i]!=0 && k==0) { k=ch[i]; continue; } if(k!=0) { k++; if(k>n) k=1; } if(ch[i]!=0 && k!=ch[i]) return 0; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int s,i,big=0,k=1,w=0,top=0,pos=0,p=0; for(i=0;i<n;i++) { ch[gondolaSeq[i]]=1; if(gondolaSeq[i]<=n) visit[i]=1; if(big<gondolaSeq[i]) big=gondolaSeq[i]; if(gondolaSeq[i]<=n) pos=i,p=gondolaSeq[i]; } for(i=0;i<n;i++) { if(visit[i]==0) { top++; arr[top].x=gondolaSeq[i]; arr[top].y=i; } } sort(arr+1,arr+top+1); if(p==0) { for(i=0;i<n;i++) a[i]=i+1; } else { for(i=pos;i<=pos+n-1;i++) { a[i%n]=p; p++; if(p==n+1) p=1; } } for(i=n+1;i<=big;i++) { if(ch[i]==0) { replacementSeq[w++]=a[arr[k].y]; a[arr[k].y]=i; } else { replacementSeq[w++]=a[arr[k].y]; a[arr[k].y]=i; k++; } } return w; } //---------------------- int countReplacement(int n, int inputSeq[]) { int s,i,big=0,k=0,w=0,top=0,pos=0,p=0; long long int dap=1,c; for(i=0;i<n;i++) { if(visit2[inputSeq[i]]==1) return 0; visit2[inputSeq[i]]=1; if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1; } for(i=1;i<=n;i++) { if(ch[i]!=0 && k==0) { k=ch[i]; continue; } if(k!=0) { k++; if(k>n) k=1; } if(ch[i]!=0 && k!=ch[i]) return 0; } k=1; memset(ch,0,sizeof ch); for(i=0;i<n;i++) { ch[inputSeq[i]]=1; if(inputSeq[i]<=n) visit[i]=1; if(big<inputSeq[i]) big=inputSeq[i]; if(inputSeq[i]<=n) pos=i,p=inputSeq[i]; } for(i=0;i<n;i++) { if(visit[i]==0) { top++; arr[top].x=inputSeq[i]; arr[top].y=i; } } sort(arr+1,arr+top+1); if(p==0) { for(i=0;i<n;i++) a[i]=i+1; dap=n; } else { for(i=pos;i<=pos+n-1;i++) { a[i%n]=p; p++; if(p==n+1) p=1; } } c=top; for(i=n+1;i<=big;i++) { if(ch[i]==1) { c--; continue; } if(c>0) dap*=c; dap%=1000000009; } return dap; }
#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...