#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+9;
const int maxn = 1e5 + 1;
//#include "gondola.h"
int valid(int n, int a[]){
for(int i = 0; i < n; i++){
if(a[i] <= n){
int j = (i + 1) % n, o = a[i] % n + 1;
set<int> s;
while(j != i){
if((a[j] <= n && a[j] != o) || s.find(a[j]) != s.end())return 0;
s.insert(a[j]);
j = (j + 1) % n;
o = o % n + 1;
}
return 1;
}
}
return 1;
}
int replacement(int n, int a[], int out[]){
pii b[n];
for(int i = 0; i < n; i++){
if(a[i] <= n){
int x = a[i] % n + 1, j = (i + 1) % n, o = 1;
while(j != i){
b[o] = {a[j], x};
x = x % n + 1;
j = (j + 1) % n;
o++;
}
break;
}
else if(i == n - 1){
for(int j = 0; j < n; j++)b[j] = {a[j], j + 1};
}
}
sort(b, b + n);
int x = b[n - 1].ff - n;
for(int i = n + 1, j = 0, o = 0; j < n; j++){
if(b[j].ff == b[j].ss)continue;
while(b[j].ff != b[j].ss){
out[o++] = b[j].ss;
b[j].ss = i;
i++;
}
}
return x;
}
int pw(int x, int y){
int ret = 1;
while(y){
if(y & 1)ret = 1ll * ret * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return ret;
}
int countReplacement(int n, int a[]){
for(int i = 0; i < n; i++){
if(a[i] <= n){
int j = (i + 1) % n, o = a[i] % n + 1;
set<int> s;
while(j != i){
if((a[j] <= n && a[j] != o) || s.find(a[j]) != s.end())return 0;
s.insert(a[j]);
j = (j + 1) % n;
o = o % n + 1;
}
break;
}
}
vt<int> hv;
for(int i = 0; i < n; i++){
if(a[i] > n){
hv.pb(a[i]);
}
}
sort(all(hv));
int sz = hv.size(), ret = pw(sz, hv[0] - n - 1);
for(int i = 1; i < sz; i++){
ret = 1ll * ret * pw(sz - i, hv[i] - hv[i - 1] - 1) % mod;
}
return ret;
}
//void solve() {
//int n;
//cin >> n;
//int a[n];
//for(int i = 0; i < n; i++){
//cin >> a[i];
//}
//cout << countReplacement(n, a);
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
Compilation message
/usr/bin/ld: /tmp/ccO9svNj.o: in function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
/usr/bin/ld: grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
/usr/bin/ld: grader.cpp:(.text.startup+0x132): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
