#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
int valid(int n, int a[]){
vector<int> b(n);
for(int i = 0; i<n; ++i) b[i] = a[i];
remove_dup(b);
if (b.size() < n) return 0;
int idx = -1;
for(int i= 0; i<n; ++i) if (a[i] <= n){
idx = (i - a[i] + n + 1) % n;
break;
}
if (idx == -1) return 1;
for(int i = 0; i<n; ++i){
int j = (idx + i) % n;
if (a[j] != i + 1 && a[j] <= n) return 0;
}
return 1;
}
int replacement(int n, int a[], int replacementSeq[]){
int idx = 0;
pair<int, int> ma = {-1, -1};
for(int i= 0; i<n; ++i) {
if (a[i] <= n) idx = (i - a[i] + n + 1) % n;
maximize(ma, make_pair(a[i], i));
}
vector<int> cur(n);
for(int i = 0; i<n; ++i){
int j = (i + idx) % n;
cur[j] = i + 1;
}
map<int, int> mp;
for(int i = 0; i<n; ++i) if (a[i] > n ) mp[a[i]] = i;
int j = 0;
for(int i = n + 1; i<=ma.first; ++i){
if (!mp.count(i)){
replacementSeq[j++] = cur[ma.second];
cur[ma.second] = i;
}
else{
int pos = mp[i];
replacementSeq[j++] = cur[pos];
cur[pos] = i;
}
}
return j;
}
const int MOD = 1e9 + 9;
ll fast_pow(ll a, ll b){
ll ans = 1;
while(b){
if (b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b /= 2;
}
return ans;
}
int countReplacement(int n, int a[]){
if (!valid(n, a)) return 0;
ll ans = 1;
int idx = -1;
for(int i= 0; i<n; ++i) if (a[i] <= n){
idx = (i - a[i] + n + 1) % n;
break;
}
if (idx == -1) ans = ans * n % MOD;
map<int, int> mp;
for(int i = 0; i<n; ++i) if (a[i] > n) mp[a[i]] = i;
int last = n;
int base = mp.size();
for(pair<int, int> i: mp){
ans = ans * fast_pow(base, i.first - last - 1) % MOD;
last = i.first;
base--;
}
return ans;
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int a[] = {2, 3, 4, 12, 6, 7, 1};
// cout << countReplacement(7, a) << "\n";
// return 0;
// }
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:52:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
52 | if (b.size() < n) return 0;
| ~~~~~~~~~^~~
# |
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 |
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 |
5 ms |
716 KB |
Output is correct |
7 |
Correct |
12 ms |
1116 KB |
Output is correct |
8 |
Correct |
10 ms |
996 KB |
Output is correct |
9 |
Correct |
3 ms |
604 KB |
Output is correct |
10 |
Correct |
11 ms |
860 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 |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
5 ms |
564 KB |
Output is correct |
7 |
Correct |
11 ms |
1116 KB |
Output is correct |
8 |
Correct |
8 ms |
860 KB |
Output is correct |
9 |
Correct |
3 ms |
604 KB |
Output is correct |
10 |
Correct |
11 ms |
860 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
5 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
11 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
348 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 |
1 ms |
548 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 |
344 KB |
Output is correct |
10 |
Correct |
1 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 |
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 |
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 |
6 ms |
860 KB |
Output is correct |
12 |
Correct |
8 ms |
1116 KB |
Output is correct |
13 |
Correct |
19 ms |
2512 KB |
Output is correct |
14 |
Correct |
7 ms |
856 KB |
Output is correct |
15 |
Correct |
21 ms |
2904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
448 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
416 KB |
Output is correct |
8 |
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 |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
448 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 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 |
27 ms |
3892 KB |
Output is correct |
10 |
Correct |
20 ms |
2924 KB |
Output is correct |
11 |
Correct |
9 ms |
1624 KB |
Output is correct |
12 |
Correct |
11 ms |
1884 KB |
Output is correct |
13 |
Correct |
3 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
424 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 |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
26 ms |
3776 KB |
Output is correct |
10 |
Correct |
22 ms |
2920 KB |
Output is correct |
11 |
Correct |
8 ms |
1628 KB |
Output is correct |
12 |
Correct |
10 ms |
1884 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
36 ms |
5356 KB |
Output is correct |
15 |
Correct |
44 ms |
6112 KB |
Output is correct |
16 |
Correct |
7 ms |
1368 KB |
Output is correct |
17 |
Correct |
27 ms |
4296 KB |
Output is correct |
18 |
Correct |
16 ms |
2524 KB |
Output is correct |