#include <bits/stdc++.h>
using namespace std;
int const mod=1e9+9;
long long power(long long a,long long b){
if(b==0)
return 1;
if(b==1)
return a;
long long pw=power(a,b/2);
pw%=mod;
pw*=pw;
pw%=mod;
if(b&1)
pw*=a;
pw%=mod;
return pw;
}
int valid(int n, int inputSeq[]){
map<int,bool> mp;
deque<int> d;
int k=n+1;
for (int i = 0; i < n; ++i)//check unique
{
d.push_back(inputSeq[i]);
if(mp[inputSeq[i]]){
return 0;
}
mp[inputSeq[i]]=1;
k=min(k,inputSeq[i]);
}
if(k==n+1)
return 1;
while(d[k-1]!=k){
d.push_front(d.back());
d.pop_back();
// cerr<<"1"<<endl;
}
// cerr<<"1"<<endl;
for (int i = 0; i < n; ++i)
if(d[i]<=n && d[i]!=i+1)
return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int maxa=0;
for (int i = 0; i < n; ++i)
maxa=max(gondolaSeq[i],maxa);
int k=n+1;
deque<int> d;
for (int i = 0; i < n; ++i)//check unique
{
d.push_back(gondolaSeq[i]);
k=min(k,gondolaSeq[i]);
}
if(k<n+1){
while(d[k-1]!=k){
d.push_front(d.back());
d.pop_back();
}
// cerr<<"set"<<endl;
}
int c=0;
set<pair<int,int>> s;
for (int i = 0; i < n; ++i)
if(d[i]>n)
s.insert({d[i],i+1});
while(s.size()){
auto p=*(s.begin());
int dd=p.first;
int cur=p.second;
s.erase(p);
while(cur<dd){
replacementSeq[c]=cur;
c++;
cur=n+c;
}
}
return c;
}
int countReplacement(int n, int inputSeq[]){
if(valid(n,inputSeq)==0)
return 0;
vector<long long> v;
long long ans=1;
for (int i = 0; i < n; ++i)
if(inputSeq[i]>n)
v.push_back(inputSeq[i]);
sort(v.begin(), v.end());
long long cur=n;
int sz=v.size();
if(sz==n)
ans=sz;
for (int i = 0; i < sz; ++i)
{
// cout<<sz-i<<' '<<(v[i]-cur)-1<<endl;
ans*=power(sz-i,(v[i]-cur)-1)%mod;
ans%=mod;
cur=v[i];
}
return ans%mod;
}
Compilation message
/usr/bin/ld: /tmp/ccwmuC1K.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
