//#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX=25e4;
int valid(int n, int a[]) {
int next=-1, ret=0;
vector<bool> occ(MAX+1);
for(int i=0; i<n; i++) {
if(occ[a[i]]) return 0;
occ[a[i]]=1;
if(next!=-1) next=next%n+1;
if(a[i]<=0) return 0;
if(a[i]<=n) {
if(next==-1) next=a[i];
if(a[i]!=next) return 0;
}
}
return 1;
}
int replacement(int n, int a[], int b[]) {
int idx=0, next=-1;
priority_queue<pair<int, int>> pq;
int init[n];
for(int i=0; i<n; i++) {
if(next!=-1) init[i]=next=next%n+1;
else if(a[i]<=n) init[i]=next=a[i];
}
if(next==-1) next=n;
for(int i=0; i<n; i++) init[i]=next=next%n+1;
for(int i=0; i<n; i++)
if(a[i]>n) pq.push({-a[i], init[i]});
next=n+1;
while(!pq.empty()) {
int u=pq.top().first, v=pq.top().second;
u=-u; b[idx++]=v;
while(next<u) b[idx++]=next++;
next++;
pq.pop();
}
return idx;
}
const int MOD=1e9+9;
int binpow(int b, int exp) {
long long base=b, ret=1;
while(exp) {
if(exp&1) ret=ret*base%MOD;
base=base*base%MOD;
exp>>=1;
}
return ret;
}
int countReplacement(int n, int a[]) {
if(!valid(n, a)) return 0;
long long ans=1;
int las=n+1, cnt=0;
priority_queue<int> pq;
for(int i=0; i<n; i++)
if(a[i]>n) pq.push(-a[i]), cnt++;
while(!pq.empty()) {
int u=-pq.top(); pq.pop();
ans=ans*binpow(cnt, u-las)%MOD;
las=u+1;
cnt--;
}
bool nperm=0;
for(int i=0; i<n; i++) if(a[i]<=n) nperm=1;
return (nperm ? 1 : n)*ans%MOD;
}
int main() {
int n; cin >> n;
int a[n]; for(int i=0; i<n; i++) cin >> a[i];
cout << countReplacement(n, a) << endl;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:6:16: warning: unused variable 'ret' [-Wunused-variable]
6 | int next=-1, ret=0;
| ^~~
/usr/bin/ld: /tmp/ccmFdZrT.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccIqw6CT.o:gondola.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccmFdZrT.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
