#include <bits/stdc++.h>
#define long long long
#include "gondola.h"
using namespace std;
const long M = 1e9+9;
int valid(int n, int inputSeq[]) {
map<int, int> M;
for(int i = 0, st = -n-1; i < n; ++i, ++st) {
M[inputSeq[i]]++;
if(st == n+1) st = 1;
if(inputSeq[i] <= n) {
if(st < 0) st = inputSeq[i];
else if(st != inputSeq[i]) return 0;
}
}
for(auto x : M) if(x.second > 1) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int sz = 0, shift = 0;
for(int i = 0; i < n; ++i) if(gondolaSeq[i] <= n) shift = i - gondolaSeq[i] + 1;
vector<int> ret(n);
for(int i = 0; i < n; ++i) ret[i] = gondolaSeq[(i + shift + n) % n];
int pos = max_element(ret.begin(), ret.end()) - ret.begin() + 1;
int mx = *max_element(ret.begin(), ret.end());
map<int, int> M;
for(int i = 0; i < n; ++i) if(ret[i] > n) M[ret[i]] = i+1;
for(int i = n+1; i <= mx; ++i) {
if(M[i] == 0 || i == mx) replacementSeq[sz++] = pos, pos = i;
else replacementSeq[sz++] = M[i];
}
return sz;
}
//----------------------
int powMod(int a, int b) {
int val = 1;
while(b) {
if(b & 1) val = (1ll * val * a) % M;
a = (1ll * a * a) % M;
b >>= 1;
}
return val;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) return 0;
vector<int> V; V.emplace_back(n);
for(int i = 0; i < n; ++i) if(inputSeq[i] > n) V.emplace_back(inputSeq[i]);
long ans = 1; int s = V.size();
sort(V.begin(), V.end());
for(int i = 1; i < s; ++i) ans = (ans * powMod(s - i, V[i] - V[i-1] - 1)) % M;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
484 KB |
Output is correct |
4 |
Correct |
2 ms |
484 KB |
Output is correct |
5 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
484 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
3 ms |
484 KB |
Output is correct |
4 |
Correct |
2 ms |
484 KB |
Output is correct |
5 |
Correct |
2 ms |
484 KB |
Output is correct |
6 |
Correct |
16 ms |
2364 KB |
Output is correct |
7 |
Correct |
13 ms |
2364 KB |
Output is correct |
8 |
Correct |
27 ms |
4116 KB |
Output is correct |
9 |
Correct |
10 ms |
4116 KB |
Output is correct |
10 |
Correct |
37 ms |
4820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4820 KB |
Output is correct |
2 |
Correct |
2 ms |
4820 KB |
Output is correct |
3 |
Correct |
2 ms |
4820 KB |
Output is correct |
4 |
Correct |
2 ms |
4820 KB |
Output is correct |
5 |
Correct |
2 ms |
4820 KB |
Output is correct |
6 |
Correct |
17 ms |
4820 KB |
Output is correct |
7 |
Correct |
16 ms |
4820 KB |
Output is correct |
8 |
Correct |
31 ms |
4820 KB |
Output is correct |
9 |
Correct |
9 ms |
4820 KB |
Output is correct |
10 |
Correct |
37 ms |
4860 KB |
Output is correct |
11 |
Correct |
2 ms |
4860 KB |
Output is correct |
12 |
Correct |
2 ms |
4860 KB |
Output is correct |
13 |
Correct |
8 ms |
4860 KB |
Output is correct |
14 |
Correct |
2 ms |
4860 KB |
Output is correct |
15 |
Correct |
21 ms |
4860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4860 KB |
Output is correct |
2 |
Correct |
3 ms |
4860 KB |
Output is correct |
3 |
Correct |
2 ms |
4860 KB |
Output is correct |
4 |
Correct |
2 ms |
4860 KB |
Output is correct |
5 |
Correct |
2 ms |
4860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4860 KB |
Output is correct |
2 |
Correct |
2 ms |
4860 KB |
Output is correct |
3 |
Correct |
2 ms |
4860 KB |
Output is correct |
4 |
Correct |
3 ms |
4860 KB |
Output is correct |
5 |
Correct |
3 ms |
4860 KB |
Output is correct |
6 |
Correct |
3 ms |
4860 KB |
Output is correct |
7 |
Correct |
4 ms |
4860 KB |
Output is correct |
8 |
Correct |
3 ms |
4860 KB |
Output is correct |
9 |
Correct |
3 ms |
4860 KB |
Output is correct |
10 |
Correct |
3 ms |
4860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4860 KB |
Output is correct |
2 |
Correct |
2 ms |
4860 KB |
Output is correct |
3 |
Correct |
2 ms |
4860 KB |
Output is correct |
4 |
Correct |
2 ms |
4860 KB |
Output is correct |
5 |
Correct |
2 ms |
4860 KB |
Output is correct |
6 |
Correct |
3 ms |
4860 KB |
Output is correct |
7 |
Correct |
2 ms |
4860 KB |
Output is correct |
8 |
Correct |
3 ms |
4860 KB |
Output is correct |
9 |
Correct |
3 ms |
4860 KB |
Output is correct |
10 |
Correct |
3 ms |
4860 KB |
Output is correct |
11 |
Correct |
13 ms |
4860 KB |
Output is correct |
12 |
Correct |
14 ms |
4860 KB |
Output is correct |
13 |
Correct |
43 ms |
4860 KB |
Output is correct |
14 |
Correct |
12 ms |
4860 KB |
Output is correct |
15 |
Correct |
66 ms |
9388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9388 KB |
Output is correct |
2 |
Correct |
3 ms |
9388 KB |
Output is correct |
3 |
Correct |
2 ms |
9388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9388 KB |
Output is correct |
2 |
Correct |
2 ms |
9388 KB |
Output is correct |
3 |
Correct |
2 ms |
9388 KB |
Output is correct |
4 |
Correct |
2 ms |
9388 KB |
Output is correct |
5 |
Correct |
2 ms |
9388 KB |
Output is correct |
6 |
Correct |
2 ms |
9388 KB |
Output is correct |
7 |
Correct |
2 ms |
9388 KB |
Output is correct |
8 |
Correct |
2 ms |
9388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9388 KB |
Output is correct |
2 |
Correct |
2 ms |
9388 KB |
Output is correct |
3 |
Correct |
3 ms |
9388 KB |
Output is correct |
4 |
Correct |
2 ms |
9388 KB |
Output is correct |
5 |
Correct |
2 ms |
9388 KB |
Output is correct |
6 |
Correct |
2 ms |
9388 KB |
Output is correct |
7 |
Correct |
3 ms |
9388 KB |
Output is correct |
8 |
Correct |
3 ms |
9388 KB |
Output is correct |
9 |
Correct |
54 ms |
9388 KB |
Output is correct |
10 |
Correct |
39 ms |
9388 KB |
Output is correct |
11 |
Correct |
16 ms |
9388 KB |
Output is correct |
12 |
Correct |
18 ms |
9388 KB |
Output is correct |
13 |
Incorrect |
5 ms |
9388 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9388 KB |
Output is correct |
2 |
Correct |
2 ms |
9388 KB |
Output is correct |
3 |
Correct |
2 ms |
9388 KB |
Output is correct |
4 |
Correct |
2 ms |
9388 KB |
Output is correct |
5 |
Correct |
2 ms |
9388 KB |
Output is correct |
6 |
Correct |
2 ms |
9388 KB |
Output is correct |
7 |
Correct |
2 ms |
9388 KB |
Output is correct |
8 |
Correct |
2 ms |
9388 KB |
Output is correct |
9 |
Correct |
55 ms |
9388 KB |
Output is correct |
10 |
Correct |
45 ms |
9388 KB |
Output is correct |
11 |
Correct |
15 ms |
9388 KB |
Output is correct |
12 |
Correct |
20 ms |
9388 KB |
Output is correct |
13 |
Incorrect |
5 ms |
9388 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |