#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 binpow(int a,int b){
int ret = 1;
while(b){
if(b & 1){
ret = (long long)ret * a%mod;
}
a = (long long)a * a % mod;
b >>= 1;
}
return ret;
}
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();
int last = n;
for(auto u:s){
ans = (long long)ans * binpow(cnt,u-last - 1)%mod;
last = u;
cnt--;
}
}
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 |
1268 KB |
Output is correct |
8 |
Correct |
16 ms |
4172 KB |
Output is correct |
9 |
Correct |
5 ms |
1492 KB |
Output is correct |
10 |
Correct |
21 ms |
4820 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 |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
8 ms |
2256 KB |
Output is correct |
7 |
Correct |
7 ms |
1232 KB |
Output is correct |
8 |
Correct |
19 ms |
4172 KB |
Output is correct |
9 |
Correct |
5 ms |
1492 KB |
Output is correct |
10 |
Correct |
20 ms |
4760 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
3 ms |
724 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
7 ms |
1232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
240 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 |
# |
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 |
1 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 |
11 |
Correct |
6 ms |
1232 KB |
Output is correct |
12 |
Correct |
8 ms |
1296 KB |
Output is correct |
13 |
Correct |
22 ms |
2532 KB |
Output is correct |
14 |
Correct |
7 ms |
1232 KB |
Output is correct |
15 |
Correct |
23 ms |
2832 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 |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 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 |
1 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 |
34 ms |
4352 KB |
Output is correct |
10 |
Correct |
33 ms |
3612 KB |
Output is correct |
11 |
Correct |
10 ms |
1580 KB |
Output is correct |
12 |
Correct |
12 ms |
1796 KB |
Output is correct |
13 |
Correct |
3 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 |
1 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 |
33 ms |
4324 KB |
Output is correct |
10 |
Correct |
27 ms |
3604 KB |
Output is correct |
11 |
Correct |
10 ms |
1532 KB |
Output is correct |
12 |
Correct |
13 ms |
1772 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
14 |
Correct |
45 ms |
5032 KB |
Output is correct |
15 |
Correct |
52 ms |
6516 KB |
Output is correct |
16 |
Correct |
9 ms |
1552 KB |
Output is correct |
17 |
Correct |
36 ms |
4396 KB |
Output is correct |
18 |
Correct |
17 ms |
2712 KB |
Output is correct |