Submission #14761

#TimeUsernameProblemLanguageResultExecution timeMemory
14761progressiveGondola (IOI14_gondola)C++98
100 / 100
30 ms3604 KiB
#include "gondola.h" #include <vector> #include <algorithm> using namespace std; int valid(int n, int inputSeq[]) { //duplication check vector<int> dupe; for(int i=0;i<n;i++) dupe.push_back(inputSeq[i]); sort(dupe.begin(),dupe.end()); for(int i=0;i<n-1;i++) if(dupe[i]==dupe[i+1]) return 0; //rotatable check int key=-1; for(int i=0;i<n;i++) if(inputSeq[i]<=n) key=i; if(key==-1) return 1; for(int i=0;i<n;i++) { if(inputSeq[i]>n) continue; if((inputSeq[i]-inputSeq[key]+n)%n!=(i-key+n)%n) return 0; //do not have same diff } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { if(!valid(n,gondolaSeq)) return 0; int key=0; for(int i=0;i<n;i++) if(gondolaSeq[i]<=n) key=i; vector<int> newSeq; for(int i=0;i<n;i++) newSeq.push_back((i+(gondolaSeq[key]-1)-key+n)%n+1); vector<pair<int,int> > targetSeq; for(int i=0;i<n;i++) if(gondolaSeq[i]>n) targetSeq.push_back(make_pair(gondolaSeq[i],i)); sort(targetSeq.begin(),targetSeq.end()); int tp=0; //top, return value for(int i=0;i<targetSeq.size();i++) { int ind=targetSeq[i].second; int val=targetSeq[i].first; while(tp+n<val) { replacementSeq[tp++]=newSeq[ind]; newSeq[ind]=tp+n; } } return tp; } //---------------------- static const int mod=1000000009; static int getpow(int a,int b) { if(b==0) return 1; long long res=getpow(a,b/2); res=(1LL*res*res)%mod; if(b%2==1) res=(1LL*res*a)%mod; return res; } int countReplacement(int n, int inputSeq[]) { if(!valid(n,inputSeq)) return 0; vector<int> p; for(int i=0;i<n;i++) if(inputSeq[i]>n) p.push_back(inputSeq[i]); sort(p.begin(),p.end()); int ginputed=n; //max gondola input long long ans=1LL; if(p.size()==n) ans=n; for(int i=0;i<p.size();i++) { ans=(1LL*ans*getpow(p.size()-i,p[i]-ginputed-1))%mod; ginputed=p[i]; } return ans; }
#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...