#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> get(int n,int inputSeq[]){
int pos = 0;
for(int i = 0;i<n;i++){
if(inputSeq[i] <= n){
pos = (i + 1 - inputSeq[i] + n)%n;
}
}
vector<int> ret;
for(int i = pos;i < n;i++){
ret.push_back(inputSeq[i]);
}
for(int i = 0;i<pos;i++){
ret.push_back(inputSeq[i]);
}
return ret;
}
int valid(int n, int inputSeq[]){
vector<int> inp = get(n,inputSeq);
set<int> s;
for(int i = 0;i<n;i++){
s.insert(inp[i]);
if(inp[i] <= n && inp[i] != i + 1){
return 0;
}
}
if(s.size() != n)
return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
vector<int> inp = get(n,gondolaSeq);
map<int,int> mp;
int maxi = 0;
for(int i = 0;i<n;i++){
if(inp[i] > n){
mp[inp[i]] = i;
if(inp[maxi] < inp[i])
maxi = i;
}
}
int l = 0;
int tmp = inp[maxi];
inp[maxi] = maxi + 1;
for(int i = n + 1;i <= tmp;i++){
if(mp.count(i) && mp[i] != maxi){
replacementSeq[l++] = mp[i] + 1;
}
else{
replacementSeq[l++] = inp[maxi];
inp[maxi] = i;
}
}
return l;
}
//----------------------
const int mod = 1e9 + 9;
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)){
return 0;
}
vector<int> inp = get(n,inputSeq);
int ans = 1;
bool ok = 1;
set<int> s;
for(int i = 0;i<n;i++){
if(inp[i] <= n){
ok = 0;
}
else s.insert(inp[i]);
}
if(ok){
ans = (long long)ans * n % mod;
}
if(s.size()){
int cnt = s.size();
for(int i = n + 1;i<=*s.rbegin();i++){
if(s.count(i)){
cnt--;
continue;
}
ans = (long long)ans * cnt % mod;
}
}
return ans;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:29:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
29 | if(s.size() != n)
| ~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
8 ms |
2384 KB |
Output is correct |
7 |
Correct |
7 ms |
1248 KB |
Output is correct |
8 |
Correct |
16 ms |
4204 KB |
Output is correct |
9 |
Correct |
5 ms |
1492 KB |
Output is correct |
10 |
Correct |
28 ms |
4860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
9 ms |
2320 KB |
Output is correct |
7 |
Correct |
7 ms |
1232 KB |
Output is correct |
8 |
Correct |
16 ms |
4176 KB |
Output is correct |
9 |
Correct |
5 ms |
1492 KB |
Output is correct |
10 |
Correct |
19 ms |
4836 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
228 KB |
Output is correct |
13 |
Correct |
3 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
7 ms |
1204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
264 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
6 ms |
1200 KB |
Output is correct |
12 |
Correct |
7 ms |
1232 KB |
Output is correct |
13 |
Correct |
20 ms |
2500 KB |
Output is correct |
14 |
Correct |
6 ms |
1232 KB |
Output is correct |
15 |
Correct |
23 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
37 ms |
4236 KB |
Output is correct |
10 |
Correct |
33 ms |
3600 KB |
Output is correct |
11 |
Correct |
13 ms |
1532 KB |
Output is correct |
12 |
Correct |
15 ms |
1792 KB |
Output is correct |
13 |
Correct |
5 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
40 ms |
4292 KB |
Output is correct |
10 |
Correct |
33 ms |
3600 KB |
Output is correct |
11 |
Correct |
13 ms |
1584 KB |
Output is correct |
12 |
Correct |
17 ms |
1804 KB |
Output is correct |
13 |
Correct |
5 ms |
596 KB |
Output is correct |
14 |
Execution timed out |
1078 ms |
5768 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |