Submission #69754

#TimeUsernameProblemLanguageResultExecution timeMemory
69754MANcityGondola (IOI14_gondola)C++14
100 / 100
137 ms9416 KiB
#include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<set> #include<stack> #include<string> #include<cstring> #include<vector> #include "gondola.h" using namespace std; #define for1(i,n) for(int i=1;i<=(int)n;i++) #define for0(i,n) for(int i=0;i<=(int)n;i++) #define forn(i,n) for(int i=n;i>=1;i--) #define fo(i,x,y) for(int i=x;i<=(int)y;i++) #define fr(i,x,y) for(int i=x;i>=(int)y;i--) #define pb push_back #define mp make_pair #define LL long long const LL Mod=1000*1000*1000+9; map<int,int> mymap; int valid(int n, int inputSeq[]) { for0(i,n-1) mymap[inputSeq[i]]++; for0(i,n-1) if(mymap[inputSeq[i]]>=2) return 0; for0(i,n-1) { if(inputSeq[i]<=n) { int N=inputSeq[i]; fo(j,i+1,n-1) { N++; if(N>n) N-=n; if(inputSeq[j]<=n && inputSeq[j]!=N) return 0; } fo(j,0,i-1) { N++; if(N>n) N-=n; if(inputSeq[j]<=n && inputSeq[j]!=N) return 0; } return 1; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { vector<pair<int,int> > V; int u=0; for0(i,n-1) { if(gondolaSeq[i]<=n) { u=1; int N=gondolaSeq[i]; fo(j,i+1,n-1) { N++; if(N>n) N-=n; V.push_back(mp(gondolaSeq[j],N)); } fo(j,0,i-1) { N++; if(N>n) N-=n; V.push_back(mp(gondolaSeq[j],N)); } break; } } if(u==0) for0(i,n-1) V.push_back(mp(gondolaSeq[i],i+1)); int q=(n+1); int num=-1; sort(V.begin(),V.end()); for0(i,V.size()-1) { if(V[i].first!=V[i].second) { int B=V[i].first; int A=V[i].second; while(A!=B) { num++; replacementSeq[num]=A; A=q; q++; } } } return (num+1); } //---------------------- LL binpow(LL x,LL n) { if(n==0) return 1; if(n%2==0) { LL A=binpow(x,n/2)%Mod; return ((LL)A*(LL)A)%Mod; } else { LL A=binpow(x,n-1)%Mod; return ((LL)A*(LL)x)%Mod; } } int countReplacement(int n, int inputSeq[]) { int t=valid(n,inputSeq); if(t==0) return 0; int qan=0; for0(i,n-1) if(inputSeq[i]<=n) qan++; if(qan==n) return 1; vector<LL> V; int u=0; for0(i,n-1) { if(inputSeq[i]<=n) { u=1; int N=inputSeq[i]; fo(j,i+1,n-1) { N++; if(N>n) N-=n; if(inputSeq[j]!=N) { V.push_back(inputSeq[j]-n-1); } } fo(j,0,i-1) { N++; if(N>n) N-=n; if(inputSeq[j]!=N) V.push_back(inputSeq[j]-n-1); } break; } } if(u==0) { for0(i,n-1) V.push_back(inputSeq[i]-n); } V.push_back(-1); sort(V.begin(),V.end()); int l=V.size(); LL ANS=1; fo(i,1,l-1) { LL B=binpow(l-i,V[i]-V[i-1]-1)%Mod; ANS=((LL)ANS*(LL)B)%Mod; ANS%=Mod; } return (ANS)%Mod; } /* 8 21 14 15 64 17 59 19 20 21 1 2 3 4 5 6 7 8 9 10 11 61 13 8 37 9 10 11 12 13 14 15 16 17 18 19 59 21 51 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 58 2 3 4 5 6 7 8 */
#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...