#include "gondola.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 250000;
int const modulo = 1000000009;
std::map<int, int> frec;
int valid(int n, int inputSeq[])
{
for(int i = 0; i < n; i++)
if(inputSeq[i] <= n) {
std::rotate(inputSeq, inputSeq + (n + i - inputSeq[i] + 1) % n, inputSeq + n);
break;
}
for(int i = 0; i < n; i++) {
if(frec[inputSeq[i]] == 1)
return false;
frec[inputSeq[i]] = 1;
if(inputSeq[i] <= n && i + 1 != inputSeq[i])
return false;
}
return true;
}
//----------------------
int seen[1 + nmax];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for(int i = 0; i < n; i++)
if(gondolaSeq[i] <= n) {
std::rotate(gondolaSeq, gondolaSeq + (n + i - gondolaSeq[i] + 1) % n, gondolaSeq + n);
break;
}
int smax = 0;
for(int i = 0; i < n; i++)
smax = MAX(smax, gondolaSeq[i]);
int pos = 0;
for(int i = 0; i < n; i++)
if(smax == gondolaSeq[i])
pos = i + 1;
for(int i = 0;i < n; i++)
seen[gondolaSeq[i]] = 1 + i;
for(int i = n + 1; i <= smax; i++)
if(seen[i] == 0) {
replacementSeq[i - n - 1] = pos;
pos = i;
} else
replacementSeq[i - n - 1] = seen[i];
return smax - n;
}
//----------------------
int lgpow(int a, int b){
if(b == 0)
return 1;
else if(b == 1)
return a;
else {
int result = lgpow(a, b / 2);
if(b % 2 == 0)
return 1LL * result * result % modulo;
else
return 1LL * result * result % modulo * a % modulo;
}
}
int countReplacement(int n, int inputSeq[])
{
if(valid(n, inputSeq) == 0)
return 0;
else {
for(int i = 0; i < n; i++)
if(inputSeq[i] <= n) {
std::rotate(inputSeq, inputSeq + (n + i - inputSeq[i] + 1) % n, inputSeq + n);
break;
}
std::vector<int> v;
for(int i = 0; i < n; i++)
if(n < inputSeq[i] )
v.push_back(inputSeq[i]);
std::sort(v.begin(), v.end());
int last = n;
int result = 1;
for(int i = 0; i < v.size(); i++){
result = 1LL * result * lgpow(v.size() - i, v[i] - 1 - last) % modulo;
last = v[i];
}
return result;
}
}
Compilation message
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v.size(); i++){
~~^~~~~~~~~~
# |
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 |
256 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 |
252 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
23 ms |
2168 KB |
Output is correct |
7 |
Correct |
14 ms |
632 KB |
Output is correct |
8 |
Correct |
37 ms |
3960 KB |
Output is correct |
9 |
Correct |
12 ms |
1528 KB |
Output is correct |
10 |
Correct |
52 ms |
4728 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 |
4 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
20 ms |
2268 KB |
Output is correct |
7 |
Correct |
13 ms |
788 KB |
Output is correct |
8 |
Correct |
41 ms |
4004 KB |
Output is correct |
9 |
Correct |
12 ms |
1528 KB |
Output is correct |
10 |
Correct |
55 ms |
4600 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
7 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
14 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 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 |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
# |
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 |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 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 |
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 |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
54 ms |
4472 KB |
Output is correct |
10 |
Correct |
44 ms |
3832 KB |
Output is correct |
11 |
Correct |
17 ms |
1656 KB |
Output is correct |
12 |
Correct |
20 ms |
1912 KB |
Output is correct |
13 |
Incorrect |
6 ms |
760 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
380 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 |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
296 KB |
Output is correct |
9 |
Correct |
55 ms |
4476 KB |
Output is correct |
10 |
Correct |
44 ms |
3804 KB |
Output is correct |
11 |
Correct |
17 ms |
1660 KB |
Output is correct |
12 |
Correct |
21 ms |
1912 KB |
Output is correct |
13 |
Incorrect |
6 ms |
760 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |