#include "gondola.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<int>;
int valid(int n, int a[]) {
set<int> x;
for (int i = 0; i < n; i++)
x.insert(a[i]);
if (x.size() != n)
return 0;
for (int i = 1; i < n; i++) {
if (a[i] > n) {
a[i] = a[i - 1] + 1;
}
}
if(*x.begin()>n)
a[0]=1;
for (int i = n; i-- > 1;) {
if (a[i] > n) {
a[i] = a[i - 1] == n ? 1 : a[i - 1] + 1;
}
}
int i = 0;
while (a[i] != 1)
i++;
int p = 1;
for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
if ((p%n)+1 != a[j])
return 0;
p = a[j];
}
return 1;
}
//----------------------
int pos[250250];
int replacement(int n, int a[], int b[]) {
int mx = 0, p = 0, mn = n, pp = 1;
bitset<250250> have;
for(int i = 0; i < n; i++) {
if(a[i]>n) {
have.set(a[i]);
pos[a[i]] = i;
}
if(a[i]>mx) mx = a[i], p = i;
if(a[i]<mn) mn = a[i], pp = i;
}
for(int i = 0; i < n; i++) {
a[pp] = mn;
mn = (mn%n)+1;
pp = (pp+1)%n;
}
for(int i = 0; i < n; i++)
if(a[i]>n) exit(-1);
int j = 0;
for(int i = n+1; i <= mx; i++) {
if(have.test(i)) {
b[j++] = a[pos[i]];
a[pos[i]] = i;
} else {
b[j++] = a[p];
a[p] = i;
}
}
return max(0, mx-n);
}
//----------------------
int ta[300300];
int countReplacement(int n, int a[]) {
for(int i = 0; i < n; i++) ta[i] = a[i];
if(!valid(n, ta)) return 0;
int mx = 0, p = 0, mn = n, pp = 0;
bitset<250250> have;
ll use = 0;
for(int i = 0; i < n; i++) {
if(a[i]>n) {
have.set(a[i]);
pos[a[i]] = i;
use++;
}
if(a[i]>mx) mx = a[i], p = i;
if(a[i]<mn) mn = a[i], pp = i;
}
for(int i = 0; i < n; i++) {
a[pp] = mn;
mn = (mn%n)+1;
pp = (pp+1)%n;
}
for(int i = 0; i < n; i++)
if(a[i]>n) exit(-1);
int j = 0;
ll ans = 1;
for(int i = n+1; i <= mx; i++) {
if(have.test(i)) {
// b[j++] = a[pos[i]];
a[pos[i]] = i;
use--;
} else {
ans = (ans*use)%1000000009;
// b[j++] = a[p];
a[p] = i;
}
}
return ans;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x.size() != n)
~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:96:6: warning: unused variable 'j' [-Wunused-variable]
int j = 0;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
16 ms |
2168 KB |
Output is correct |
7 |
Correct |
38 ms |
3704 KB |
Output is correct |
8 |
Correct |
29 ms |
3960 KB |
Output is correct |
9 |
Correct |
10 ms |
1528 KB |
Output is correct |
10 |
Correct |
36 ms |
4600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
17 ms |
2296 KB |
Output is correct |
7 |
Correct |
37 ms |
3704 KB |
Output is correct |
8 |
Correct |
29 ms |
3960 KB |
Output is correct |
9 |
Correct |
10 ms |
1400 KB |
Output is correct |
10 |
Correct |
37 ms |
4600 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
20 ms |
2180 KB |
Output is correct |
14 |
Correct |
2 ms |
256 KB |
Output is correct |
15 |
Correct |
48 ms |
4728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
380 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
12 ms |
632 KB |
Output is correct |
12 |
Correct |
14 ms |
632 KB |
Output is correct |
13 |
Correct |
15 ms |
1528 KB |
Output is correct |
14 |
Correct |
11 ms |
632 KB |
Output is correct |
15 |
Correct |
22 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |