# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
152493 | 2019-09-08T08:19:42 Z | Nightlight | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KB |
#include "gondola.h" #include <bits/stdc++.h> #define MOD 1000000009; using namespace std; int exist[250001]; int valid(int n, int inputSeq[]) { int idx = 0; for(int i = 0; i < n; i++){ if(!idx && inputSeq[i] <= n) idx = inputSeq[i]; else{ if(idx > n)idx = 1; if(inputSeq[i] <= n && inputSeq[i] != idx) return 0; idx++; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int len = 0, idx = 0, av = 0, MAX = 0, MAXid; for(int i = 0; i < n; i++){ if(gondolaSeq[i] <= n){ idx = gondolaSeq[i] - i; if(idx < 1) idx += n; break; } } if(!idx)idx = 1; for(int i = 0; i < n; i++){ if(idx > n)idx = 1; if(gondolaSeq[i] > MAX){ MAX = gondolaSeq[i]; MAXid = idx; } if(gondolaSeq[i] > n){ exist[gondolaSeq[i]] = idx; // cout << gondolaSeq[i] << " " << exist[gondolaSeq[i]] << "\n"; } idx++; } if(MAX == n)return 0; else{ int j = 0, MAXin = 0, last = 0; exist[MAX] = 0; for(int i = n+1; i <= MAX; i++){ // cout << i << " " << exist[i] << "\n"; if(exist[i]){ replacementSeq[i-n-1] = exist[i]; }else{ if(!MAXin){ replacementSeq[i-n-1] = MAXid; MAXin = 1; }else{ replacementSeq[i-n-1] = last; } last = i; } } } return MAX - n; } //---------------------- vector<int> replaced; long long int pow( long long int a, long long int x ){ if( x == 0 || a == 1 ) return 1; if( x % 2 ) return ( pow( a, x - 1 ) * a ) % MOD; long long int h = pow( a, x/2 ); return ( h * h ) % MOD; } int countReplacement(int n, int inputSeq[]) { int idx = 0; replaced.push_back(n); for(int i = 0; i < n; i++){ if(!idx && inputSeq[i] <= n) idx = inputSeq[i]; else{ if(idx > n)idx = 1; if(inputSeq[i] > n)replaced.push_back[inputSeq[i]]; else if(inputSeq[i] <= n && inputSeq[i] != idx) return 0; idx++; } } sort(replaced.begin(), replaced.end()); long long ans = idx ? n : 1; if(!idx){ ans *= n; } for(int i = 1; i < replaced.size(); i++){ ans *= pow(replaced.size() - i + 1,replaced[i] - replaced[i-1]); ans %= MOD; } return ans; }