#include <bits/stdc++.h>
using namespace std;
//#include "gondola.h"
#define mp make_pair
#define st first
#define nd second
#define ll long long
const int mod = 1e9 + 9;
const int N = 2e5 + 5;
pair < int , int > P[N],mn;
int T[N],j;
int valid(int n, int *A){
int i;
mn = mp(mod,0);
map < int , int > M;
M.clear();
for(i=0;i<n;i++){
mn = min(mn , mp(A[i],i));
if(M[ A[i] ]) return 0;
M[ A[i] ] = 1;
}
if(mn.st > n) { j = 0; return 1; }
j = mn.nd - mn.st+1;
if(j < 0) j += n;
for(i=0;i<n;i++)
if(A[i] <= n && ((j+A[i]-1 < n && j+A[i]-1 != i)||(j+A[i]-1 >= n && j+A[i]-1-n != i)) )
return 0;
return 1;
}
ll fast(ll a, ll b){
ll t=1;
for(; b ; b>>=1){
if(b & 1) t = t*a % mod;
a = a*a % mod;
}
return t;
}
int countReplacement(int n, int *A){
if(valid(n,A) == 0) return 0;
long long ans=1;
int i,x,y;
for(i=0;i<n;i++) T[i] = A[i];
sort(T,T+n);
for(i=n-1;i>=0;i--){
x = T[i];
if(x <= n) break;
y = i && T[i-1] > n ? T[i-1] : n;
ans = ans * fast(n-i,x-y-1) % mod;
}
if(i == -1) ans = ans * n % mod;
return ans;
}
int replacement(int n, int *A, int *B){
if(valid(n,A) == 0) return 0;
int i,x,y,z, b=0;
for(i=0;i<n;i++) P[i] = mp(A[i],i);
sort(P,P+n);
y = n+1;
for(i=0;i<n;i++){
x = P[i].st;
if(x <= n) continue;
z = P[i].nd-j+1;
if(z <= 0) z += n;
// cout << j << " " << P[i].nd << " " <<x << " " << z << " ss\n";
B[b++] = z;
for(; y<x ; y++) B[b++] = y;
y++;
}
return b;
}
Compilation message
/tmp/ccTZayI2.o: In function `main':
grader.cpp:(.text.startup+0xc3): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0xe2): undefined reference to `valid'
grader.cpp:(.text.startup+0x106): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
