// M
#include<bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int N = 300005, Mod = 1e9 + 9;
int n, A[N];
int valid(int _n, int inputSeq[])
{
n = _n;
for (int i = 0; i < n; i ++)
A[i] = inputSeq[i] - 1;
int st = -1;
map < int , int > MP;
for (int i = 0; i < n; i ++)
{
if (MP[A[i]])
return 0;
MP[A[i]] = 1;
if (A[i] < n)
st = i;
}
if (st == -1)
return 1;
for (int i = 0; i < n; i ++)
if (A[i] < n)
{
if (i <= st && (A[i] + st - i) % n != A[st])
return 0;
if (i > st && (A[st] + i - st) % n != A[i])
return 0;
}
return 1;
}
int replacement(int _n, int gondolaSeq[], int replacementSeq[])
{
n = _n;
for (int i = 0; i < n; i ++)
A[i] = gondolaSeq[i] - 1;
int st = -1;
for (int i = 0; i < n; i ++)
if (A[i] < n)
st = (i - A[i] + n) % n;
vector < int > M(N, -1);
for (int i = 0; i < n; i ++)
M[A[i]] = i;
int ptr = N - 1, fre = N - 1;
vector < int > V;
while (ptr >= n)
{
while (M[ptr] == -1 && ptr >= n)
ptr --;
if (ptr < n)
break;
fre = min(fre, ptr - 1);
int nw = M[ptr]; ptr --;
while (M[fre] != -1 && fre >= n)
fre --;
if (fre < n && st != -1)
{
V.push_back((nw - st + n) % n);
continue;
}
M[fre] = nw;
V.push_back(fre);
}
reverse(V.begin(), V.end());
for (int i = 0; i < (int)V.size(); i ++)
replacementSeq[i] = V[i] + 1;
return ((int)V.size());
}
int Power(int a, int b)
{
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % Mod)
if (b & 1) ret = 1LL * ret * a % Mod;
return ret;
}
int countReplacement(int _n, int inputSeq[])
{
n = _n;
for (int i = 0; i < n; i ++)
A[i] = inputSeq[i];
if (!valid(n, A))
return 0;
vector < int > V;
for (int i = 0; i < n; i ++)
V.push_back(A[i]);
sort(V.begin(), V.end());
reverse(V.begin(), V.end());
bool ff = 0;
while ((int)V.size() && (int)V.back() < n)
V.pop_back(), ff = 1;
V.push_back(n - 1);
int tot = 1;
for (int i = 1; i < (int)V.size(); i ++)
tot = 1LL * tot * Power(i, V[i - 1] - V[i] - 1) % Mod;
if (!ff)
tot = 1LL * tot * n % Mod;
return tot;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
16 ms |
2432 KB |
Output is correct |
7 |
Correct |
15 ms |
1024 KB |
Output is correct |
8 |
Correct |
33 ms |
4216 KB |
Output is correct |
9 |
Correct |
12 ms |
1536 KB |
Output is correct |
10 |
Correct |
38 ms |
4864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
18 ms |
2432 KB |
Output is correct |
7 |
Correct |
14 ms |
1024 KB |
Output is correct |
8 |
Correct |
34 ms |
4480 KB |
Output is correct |
9 |
Correct |
9 ms |
1536 KB |
Output is correct |
10 |
Correct |
37 ms |
4856 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
21 ms |
2304 KB |
Output is correct |
14 |
Correct |
0 ms |
384 KB |
Output is correct |
15 |
Correct |
59 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1536 KB |
Output is correct |
2 |
Correct |
1 ms |
1536 KB |
Output is correct |
3 |
Correct |
1 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1536 KB |
Output is correct |
2 |
Correct |
1 ms |
1536 KB |
Output is correct |
3 |
Correct |
1 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1536 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1536 KB |
Output is correct |
8 |
Incorrect |
2 ms |
1536 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1536 KB |
Output is correct |
2 |
Correct |
1 ms |
1536 KB |
Output is correct |
3 |
Correct |
1 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1536 KB |
Output is correct |
6 |
Correct |
2 ms |
1536 KB |
Output is correct |
7 |
Correct |
2 ms |
1536 KB |
Output is correct |
8 |
Incorrect |
2 ms |
1536 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
56 ms |
4344 KB |
Output is correct |
10 |
Correct |
48 ms |
3720 KB |
Output is correct |
11 |
Correct |
15 ms |
1536 KB |
Output is correct |
12 |
Correct |
18 ms |
1792 KB |
Output is correct |
13 |
Correct |
4 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
71 ms |
4360 KB |
Output is correct |
10 |
Correct |
43 ms |
3704 KB |
Output is correct |
11 |
Correct |
15 ms |
1564 KB |
Output is correct |
12 |
Correct |
18 ms |
1792 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Correct |
83 ms |
4912 KB |
Output is correct |
15 |
Correct |
84 ms |
5496 KB |
Output is correct |
16 |
Correct |
12 ms |
1280 KB |
Output is correct |
17 |
Correct |
51 ms |
3836 KB |
Output is correct |
18 |
Correct |
25 ms |
2304 KB |
Output is correct |