#include <bits/stdc++.h>
//~ #include "gondola.h"
#define ll long long
#define mod 1000000009
using namespace std;
int n;
int inputSeq[1000];
int binpow(ll x,ll y){
if( y == 0 ) return 1;
ll res = binpow(x,y/2);
res *= res;
res %= mod;
if( y % 2 ) res *= x;
return res%mod;
}
int replacement(int n, int inputSeq[], int replacementSeq[]){
int mn = INT_MAX;
int id;
for(int i = 0 ; i < n ; i++){
if( mn > inputSeq[i] ){
mn = inputSeq[i];
id = i;
}
}
vector<int> v;
mn--;
id = (id-mn)%n+n;
id %= n;
for(int i = id ; i < n ; i++) v.push_back(inputSeq[i]);
for(int i = 0 ; i < id ; i++) v.push_back(inputSeq[i]);
priority_queue<pair<int,int>> pq;
for(int i = 0 ; i < n ; i++){
pq.push({-v[i],i+1});
}
int mx = *max_element(v.begin(),v.end());
if( mx == n ) return 0;
int cur = n+1;
int ti = 0;
while(!pq.empty()){
int fufu = pq.top().second;
while(cur <= -pq.top().first){
replacementSeq[ti] = fufu;
fufu = cur;
ti++;
cur++;
}
pq.pop();
}
//~ for(int i = 0; i < mx-n ; i++){
//~ cout<<replacementSeq[i]<<" ";
//~ }
//~ cout<<"\n";
return mx-n;
}
int valid(int n,int inputSeq[]){
int mn = INT_MAX;
int id;
map<int,int> cnt;
for(int i = 0 ; i < n ; i++){
cnt[inputSeq[i]]++;
if( cnt[inputSeq[i]] > 1 ) return 0;
}
for(int i = 0 ; i < n ; i++){
if( mn > inputSeq[i] ){
mn = inputSeq[i];
id = i;
}
}
if( mn > n ) return 1;
vector<int> v;
mn--;
id = (id-mn)%n+n;
id %= n;
for(int i = id ; i < n ; i++) v.push_back(inputSeq[i]);
for(int i = 0 ; i < id ; i++) v.push_back(inputSeq[i]);
for(int i = 0 ; i < n ; i++){
if( v[i] <= n && v[i] != i+1 ) return 0;
}
return 1;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)) return 0;
ll mx = 0;
for(int i = 0 ; i < n ; i++){
mx = max((ll)inputSeq[i],mx);
}
ll u = *min_element(inputSeq,inputSeq+n);
mx -= n;
ll c = 0;
for(int i = 0 ; i < n ; i++){
int x = inputSeq[i];
if( x > n ) {
c++;
mx--;
}
}
ll fact[n+5];
fact[0] = 1;
fact[1] = 1;
for(ll i = 2; i <= n ; i++){
fact[i] = fact[i-1]*i;
fact[i] %= mod;
}
if( u > n ) return (binpow(fact[c],mx)*fact[n])%mod;
else return binpow(fact[c],mx)%mod;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i = 0 ; i < n ; i++){
cin>>inputSeq[i];
}
cout<<countReplacement(n,inputSeq)<<"\n";
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:29:11: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
29 | id = (id-mn)%n+n;
| ~~~^~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:75:11: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | id = (id-mn)%n+n;
| ~~~^~~~
/usr/bin/ld: /tmp/ccUiuQfi.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccB6ePwh.o:gondola.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUiuQfi.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
