#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]){
vector<pair<int, int>>p;
map<int, bool>cnt;
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) == 0){
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;
}
const int mod = 1e9 + 7;
int power(int a, int b){
int ans = 1;
for(; b > 0; b >>= 1, a = 1LL * a * a % mod){
if(b & 1){
ans = 1LL * ans * a % mod;
}
}
return ans;
}
int countReplacement(int n, int inputSeq[]){
if(valid(n, inputSeq) == 0){
return 0;
}
vector<int>p;
for(int i = 0; i < n; i++){
if(inputSeq[i] > n){
p.emplace_back(i);
}
}
sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
return inputSeq[i] < inputSeq[j];
});
int ans = 1;
for(int i = 0, pre = n; i < p.size(); pre = inputSeq[p[i++]]){
ans = 1LL * ans * power(int(p.size()) - i, inputSeq[p[i]] - pre - 1) % mod;
}
if(p.size() == n){
ans = 1LL * ans * n % mod;
}
return ans;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:19: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]
19 | for(int i = 1; i < p.size(); i++){
| ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:94:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 0, pre = n; i < p.size(); pre = inputSeq[p[i++]]){
| ~~^~~~~~~~~~
gondola.cpp:97:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | if(p.size() == n){
| ~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
504 KB |
Output is correct |
2 |
Correct |
1 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
9 ms |
1240 KB |
Output is correct |
7 |
Correct |
19 ms |
1744 KB |
Output is correct |
8 |
Correct |
9 ms |
1748 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
12 ms |
1744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
1084 KB |
Output is correct |
7 |
Correct |
13 ms |
1776 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 |
1900 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
14 ms |
2084 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
17 ms |
2260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
504 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
9 ms |
1748 KB |
Output is correct |
12 |
Correct |
11 ms |
1788 KB |
Output is correct |
13 |
Correct |
21 ms |
2652 KB |
Output is correct |
14 |
Correct |
9 ms |
1748 KB |
Output is correct |
15 |
Correct |
20 ms |
2832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
360 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |