#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]){
vector<pair<int, int>>p;
const int LIM = 250001;
vector<bool>cnt(LIM, false);
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n){
p.emplace_back(inputSeq[i], i);
}
else if(cnt[inputSeq[i]]){
return 0;
}
else{
cnt[inputSeq[i]] = true;
}
}
sort(p.begin(), p.end());
for(int i = 1; i < p.size(); i++){
if((p[i].second < p[i - 1].second && (p[i].second += n) < p[i - 1].second) || (p[i].second - p[i - 1].second != p[i].first - p[i - 1].first)){
return 0;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
if(!valid(n, gondolaSeq)){
return 0;
}
int index = min_element(gondolaSeq, gondolaSeq + n) - gondolaSeq, L = 0;
if(gondolaSeq[index] > n){
vector<int>p(n), init(n);
iota(p.begin(), p.end(), 0);
iota(init.begin(), init.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
return gondolaSeq[i] < gondolaSeq[j];
});
int current = n;
for(int& i : p){
while(gondolaSeq[i] > init[i]){
replacementSeq[L++] = init[i];
init[i] = ++current;
}
}
}
else{
vector<int>init(n);
for(int i = 0; i < n; i++){
init[(i + index) % n] = (gondolaSeq[index] - 1 + i) % n + 1;
}
vector<int>p;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] > n){
p.emplace_back(i);
}
}
sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
return gondolaSeq[i] < gondolaSeq[j];
});
int current = n;
for(int& i : p){
while(gondolaSeq[i] > init[i]){
replacementSeq[L++] = init[i];
init[i] = ++current;
}
}
}
return L;
}
int countReplacement(int n, int inputSeq[]){
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 1; i < p.size(); i++){
| ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
72 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
444 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
1132 KB |
Output is correct |
7 |
Correct |
12 ms |
1748 KB |
Output is correct |
8 |
Correct |
8 ms |
1748 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
12 ms |
1748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
504 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
1240 KB |
Output is correct |
7 |
Correct |
13 ms |
1748 KB |
Output is correct |
8 |
Correct |
8 ms |
1892 KB |
Output is correct |
9 |
Correct |
4 ms |
856 KB |
Output is correct |
10 |
Correct |
12 ms |
1748 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
3 ms |
444 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
11 ms |
1240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
544 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
448 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
9 ms |
2260 KB |
Output is correct |
12 |
Correct |
11 ms |
2768 KB |
Output is correct |
13 |
Correct |
11 ms |
1520 KB |
Output is correct |
14 |
Correct |
9 ms |
2260 KB |
Output is correct |
15 |
Correct |
16 ms |
2464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |