Submission #31171

#TimeUsernameProblemLanguageResultExecution timeMemory
31171cscandkswonGondola (IOI14_gondola)C++14
100 / 100
36 ms4952 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; const int MAXN=100000; const long long MOD=1000000009; int init[MAXN]; void settinginit(int n, int seq[]){ int i, x=-1; for(i=0; i<n; i++)if(seq[i]<=n){ x=(i-seq[i]+1+n)%n; break; } if(x==-1) x=0; for(i=0; i<n; i++, x=(x+1)%n) init[x]=i+1; } int valid(int n, int inputSeq[]){ int i; settinginit(n, inputSeq); for(i=0; i<n; i++) if(inputSeq[i]<=n&&inputSeq[i]!=init[i]) return 0; sort(inputSeq, inputSeq+n); for(i=1; i<n; i++) if(inputSeq[i-1]==inputSeq[i]) return 0; return 1; } pair<int, int> rep[MAXN]; int replacement(int n, int gondolaSeq[], int replacementSeq[]){ int i, length=0, change=0, last=n+1; settinginit(n, gondolaSeq); for(i=0; i<n; i++) if(gondolaSeq[i]!=init[i]) rep[change].first=gondolaSeq[i], rep[change++].second=i; sort(rep, rep+change); for(i=0; i<change; i++){ replacementSeq[length++]=init[rep[i].second]; for(; last<rep[i].first; last++) replacementSeq[length++]=last; last=rep[i].first+1; } return length; } int plc[MAXN], st[50]; int getpow(int a, int b){ int i, ans=1; st[0]=a; for(i=1; (1<<i)<=b; i++) st[i]=(long long)st[i-1]*st[i-1]%MOD; for(i=0; (1<<i)<=b; i++){ if((1<<i)&b){ ans=(long long)ans*st[i]%MOD; } } return ans; } int countReplacement(int n, int inputSeq[]){ long long count=1; int i, change=0, last=n+1, o=1; if(valid(n, inputSeq)==0) return 0; if(inputSeq[0]>n) o=n; for(i=0; i<n; i++) if(inputSeq[i]>=n) plc[change++]=inputSeq[i]; sort(plc, plc+change); for(i=0; i<change; i++){ count=count*getpow((change-i), (plc[i]-last))%MOD; last=plc[i]+1; } return count*o%MOD; }
#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...