Submission #18703

#TimeUsernameProblemLanguageResultExecution timeMemory
18703suhgyuho_williamGondola (IOI14_gondola)C++98
100 / 100
83 ms8112 KiB
#include "gondola.h" #include <algorithm> #include <map> using namespace std; map<int,bool> Map; int valid(int n, int inputSeq[]) { int i; int s,t; s = -1; for(i=0; i<n; i++){ if(Map.find(inputSeq[i]) != Map.end()) return 0; Map[inputSeq[i]] = true; if(inputSeq[i] <= n){ t = i+2-inputSeq[i]; if(t <= 0) t += n; if(s == -1){ s = t; }else if(s != t){ return 0; } } } return 1; } //---------------------- struct datar{ int num,value; }a[100002]; bool cmp(datar x,datar y){ return x.value < y.value; } int first[100002]; int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int i,j,cnt; int s,t,big,nnum; s = -1; for(i=0; i<n; i++){ if(gondolaSeq[i] <= n){ t = i+2-gondolaSeq[i]; if(t <= 0) t += n; s = t; break; } } big = 0; for(i=0; i<n; i++) big = max(big,gondolaSeq[i]); if(big == n){ return 0; } for(i=n; i>=1; i--) gondolaSeq[i] = gondolaSeq[i-1]; cnt = 0; if(s == -1) s = 1; first[s] = 1; for(i=1; i<n; i++){ t = s+i; if(t > n) t -= n; first[t] = i+1; } for(i=1; i<=n; i++){ a[i].num = i; a[i].value = gondolaSeq[i]; } sort(a+1,a+n+1,cmp); nnum = n+1; if(a[1].value > n){ replacementSeq[cnt] = first[a[1].num]; cnt++; nnum++; for(i=nnum; i<=a[1].value; i++){ replacementSeq[cnt] = nnum-1; cnt++; nnum++; } } for(i=2; i<=n; i++){ if(a[i].value <= n) continue; replacementSeq[cnt] = first[a[i].num]; cnt++; nnum++; for(j=nnum; j<=a[i].value; j++){ replacementSeq[cnt] = nnum-1; cnt++; nnum++; } } return cnt; } //---------------------- #define MOD 1000000009; long long mul(long long x,long long y){ // return x^y; if(y == 0) return 1; if(y == 1) return x; long long tmp = mul(x,y/2); tmp *= tmp; tmp %= MOD; if(y%2 == 1){ tmp *= x; tmp %= MOD; } return tmp; } long long ans; int countReplacement(int n, int inputSeq[]) { if(valid(n,inputSeq) == 0) return 0; int i,j,t; int s,big; long long x,nnum; s = -1; for(i=0; i<n; i++){ if(inputSeq[i] <= n){ s = i+2-inputSeq[i]; if(s <= 0) s += n; break; } } big = 0; for(i=0; i<n; i++) big = max(big,inputSeq[i]); if(big == n){ return 1; } if(s == -1){ s = 1; ans = (long long)n; }else ans = 1; for(i=n; i>=1; i--) inputSeq[i] = inputSeq[i-1]; first[s] = 1; for(i=1; i<n; i++){ t = s+i; if(t > n) t -= n; first[t] = i+1; } for(i=1; i<=n; i++){ a[i].num = i; a[i].value = inputSeq[i]; } sort(a+1,a+n+1,cmp); nnum = n+1; x = (long long)n; if(a[1].value > n){ nnum++; ans *= mul(x,(long long)(a[1].value-nnum+1)); ans %= MOD; nnum = a[1].value+1; } x--; for(i=2; i<=n; i++){ if(a[i].value <= n){ x--; continue; } nnum++; ans *= mul(x,(long long)(a[i].value-nnum+1)); ans %= MOD; nnum = a[i].value+1; x--; } return (int)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...