#include <bits/stdc++.h>
#include "gondola.h"
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 1e6 + 10, mod = 1e9 + 9;
int a[maxn];
int bio[maxn];
vector <pair<int, int> > v;
int mul(int x, int y){
return ((ll)x * y) % mod;
}
int valid(int n, int inputSeq[]){
for(int i = 0; i < n; i++){
a[i] = inputSeq[i] - 1;
if(bio[a[i]]) return 0;
bio[a[i]] = 1;
}
for(int i = 0; i < n; i++){
if(a[i] < n){
for(int j = 0; j < n; j++){
if(a[(i + j) % n] < n){
if(a[(i + j) % n] != (a[i] + j) % n) return 0;
}
}
break;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
for(int i = 0; i < n; i++){
a[i] = gondolaSeq[i];
}
for(int i = 0; i < n; i++){
if(a[i] > n) v.push_back({a[i], i});
}
for(int i = n - 1; i >= 0; i--){
if(a[i] <= n || !i){
for(int j = 0; j < n; j++){
a[(i + j) % n] = (a[i] - 1 + j) % n + 1;
}
break;
}
}
// cout << v.size() << endl;
sort(v.begin(), v.end());
int p = 0, l = 0;
while(p < v.size()){
replacementSeq[l] = a[v[p].se];
// cout << a[v[p].se] << ' ';
a[v[p].se] = n + l + 1;
l++;
if(a[v[p].se] == v[p].fi) p++;
}
// cout << endl;
// cout << l;
return l;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
for(int i = 0; i < n; i++){
a[i] = inputSeq[i];
}
for(int i = 0; i < n; i++){
if(a[i] > n) v.push_back({a[i], i});
}
// for(int i = n - 1; i >= 0; i--){
// if(a[i] <= n || !i){
// for(int j = 0; j < n; j++){
// a[(i + j) % n] = (a[i] - 1 + j) % n + 1;
// }
// break;
// }
// }
// cout << v.size() << endl;
// cout << v.size() << endl;
// if(v.size() == 0) return 1;
sort(v.begin(), v.end());
// for(int i = 0; i < v.size(); i++){
// cout << v[i].fi << ' ' << v[i].se << endl;
// }
int p = 0, l = n, ans = 1;
while(p < v.size()){
l++;
if(a[v[p].se] == l){
p++;
continue;
}
ans = mul(ans, v.size() - p);
}
// cout << endl;
// cout << l;
// if(v.size() == n) ans = mul(ans, n);
return ans;
}
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//
// int n;
// cin >> n;
// int inputSeq[n];
// for(int i = 0; i < n; i++){
// cin >> inputSeq[i];
// }
// cout << countReplacement(n, inputSeq);
//
// return 0;
//}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while(p < v.size()){
| ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:115:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while(p < v.size()){
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 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 |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
6 ms |
1116 KB |
Output is correct |
8 |
Correct |
5 ms |
1296 KB |
Output is correct |
9 |
Correct |
2 ms |
856 KB |
Output is correct |
10 |
Correct |
6 ms |
1372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 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 |
6 |
Correct |
3 ms |
856 KB |
Output is correct |
7 |
Correct |
6 ms |
1116 KB |
Output is correct |
8 |
Correct |
5 ms |
1108 KB |
Output is correct |
9 |
Correct |
4 ms |
600 KB |
Output is correct |
10 |
Correct |
6 ms |
1372 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 |
1372 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
8 ms |
1372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 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 |
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 |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 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 |
344 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 |
11 |
Correct |
6 ms |
860 KB |
Output is correct |
12 |
Correct |
9 ms |
1116 KB |
Output is correct |
13 |
Correct |
10 ms |
1616 KB |
Output is correct |
14 |
Correct |
6 ms |
860 KB |
Output is correct |
15 |
Correct |
13 ms |
2524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 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 |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 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 |
0 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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
11 ms |
2264 KB |
Output is correct |
10 |
Correct |
11 ms |
2004 KB |
Output is correct |
11 |
Correct |
5 ms |
1624 KB |
Output is correct |
12 |
Correct |
5 ms |
1496 KB |
Output is correct |
13 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
14 |
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 |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
11 ms |
2264 KB |
Output is correct |
10 |
Correct |
9 ms |
2004 KB |
Output is correct |
11 |
Correct |
5 ms |
1628 KB |
Output is correct |
12 |
Correct |
5 ms |
1496 KB |
Output is correct |
13 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |