# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
152494 | 2019-09-08T08:20:34 Z | Nightlight | Gondola (IOI14_gondola) | C++14 | 23 ms | 2808 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 idx = 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 400 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 3 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 400 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 3 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 380 KB | Output is correct |
11 | Correct | 12 ms | 1144 KB | Output is correct |
12 | Correct | 13 ms | 1144 KB | Output is correct |
13 | Correct | 15 ms | 1628 KB | Output is correct |
14 | Correct | 12 ms | 1144 KB | Output is correct |
15 | Correct | 23 ms | 2808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |