#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
typedef long long lld;
static const int MOD = 1e9 + 9;
static int tmp[MAXN];
int valid(int n,int inputSeq[])
{
int i,j,p = -1;
for (i=0;i<n;i++){
tmp[i] = inputSeq[i];
if (inputSeq[i] <= n){
j = (i-inputSeq[i]+1+n)%n;
if (p < 0) p = j;
else if (p != j) return 0;
}
}
sort(tmp,tmp+n);
for (i=1;i<n;i++) if (tmp[i-1] == tmp[i]) return 0;
return 1;
}
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
if (!valid(n,gondolaSeq)) return -1;
int i,j,p = -1;
for (i=0;i<n;i++){
if (gondolaSeq[i] <= n){
j = (i-gondolaSeq[i]+1+n)%n;
if (p < 0) p = j;
else if (p != j) return 0;
}
}
int y=0;
for (i=0;i<n;i++) if (gondolaSeq[i] > n){
if (y < gondolaSeq[i]) y = gondolaSeq[i];
}
if (!y) return 0;
map<int,int> pos;
for (i=0;i<n;i++) pos[gondolaSeq[i]] = i;
if (p == -1) p = 0;
int c = 0, t = pos[y];
for (i=0;i<n;i++) tmp[i] = (i-p+n)%n+1;
for (i=n+1;i<=y;i++){
int x = pos.count(i) ? pos[i] : t;
replacementSeq[c++] = tmp[x];
tmp[x] = i;
}
return y-n;
}
int pow(int a,int b)
{
int ret = 1,t = a,i;
for (i=0;i<31;i++,t=(lld)t*t%MOD) if (b&(1<<i)){
ret = (lld)ret*t%MOD;
}
return ret;
}
int countReplacement(int n,int inputSeq[])
{
if (!valid(n,inputSeq)) return 0;
int ret = 1,last = n,i;
vector <int> a;
for (i=0;i<n;i++){
if (inputSeq[i] <= n) ret = n;
else a.pb(inputSeq[i]);
}
sort(all(a));
int left = sz(a);
for (i=0;i<sz(a);i++){
int dummy = a[i] - last - 1;
ret = ((lld)ret*pow(left,dummy))%MOD;
last = a[i]; left--;
}
return ret;
}
Compilation message
/tmp/ccyWbJSZ.o: In function `main':
grader.cpp:(.text.startup+0xb1): undefined reference to `replacement'
grader.cpp:(.text.startup+0x141): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0x164): undefined reference to `valid'
collect2: ld returned 1 exit status
