#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
const int inf=1e9;
const int mod=1e9+9;
int replacement(int n, int a[], int r[]) {
int m=inf;
forn(i,n) m=min(m,a[i]);
if (m>n) {
vector<int> p;
set<int> s;
forn(i,n) s.insert(i);
map<int,int> mp;
forn(i,n) mp[a[i]]=i;
int l=0; forn(i,n) l=max(l,a[i]);
vector<int> v(n); forn(i,n) v[i]=i+1;
for (int i=n+1; i<=l; ++i) {
if (mp.count(i)) {
p.pb(v[mp[i]]);
s.erase(mp[i]);
} else {
p.pb(v[*s.begin()]);
v[*s.begin()]=i;
}
}
forn(i,p.size()) r[i]=p[i];
return p.size();
}
vector<int> p;
set<int> s;
forn(i,n) if (a[i]>n) s.insert(i);
map<int,int> mp;
forn(i,n) mp[a[i]]=i;
int l=0; forn(i,n) l=max(l,a[i]);
int z=-1;
forn(i,n) if (a[i]<=n) z=i;
vector<int> v(n);
if (z==-1) forn(i,n) v[i]=i+1;
else forn(i,n) v[i]=((a[z]-1+i-z+n)%n)+1;
for (int i=n+1; i<=l; ++i) {
if (mp.count(i)) {
p.pb(v[mp[i]]);
s.erase(mp[i]);
} else {
p.pb(v[*s.begin()]);
v[*s.begin()]=i;
}
}
forn(i,p.size()) r[i]=p[i];
return p.size();
}
ll pw(ll a, ll b) {
ll r=1;
while(b) {
if (b&1) r=(1ll*r*a)%mod;
a=(1ll*a*a)%mod;
b>>=1;
}
return r;
}
int countReplacement(int n, int a[]) {
vector<int> s; forn(i,n) s.pb(a[i]);
sort(all(s));
forn(i,n-1) if (s[i]==s[i+1]) return 0;
int m=inf;
forn(i,n) m=min(m,a[i]);
if (m>n) {
vector<int> v; forn(i,n) v.pb(a[i]);
sort(all(v));
ll ans=1;
int k=n;
int l=n;
for(auto&x:v) {
ans=(1ll*ans*pw(k,x-l-1))%mod;
--k;
l=x;
}
ans=(ans*n)%mod;
return ans;
}
int i=0;
for(;i<n;++i) if (a[i]<=n) break;
i-=a[i]-1;
if (i<0) i+=n;
vector<int> v;
int z=1;
for (int j=i; j<i+n; ++j) {
if (a[j%n]<=n) z&=a[j%n]==j-i+1;
else v.pb(a[j%n]);
}
if (!z) return 0;
if (!v.size()) return 1;
sort(all(v));
int k=v.size();
ll ans=1;
int l=n;
for(auto&x:v) {
ans=(1ll*ans*pw(k,x-l-1))%mod;
--k;
l=x;
}
return ans;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define forn(i,n) for(int i=0;i<n;++i)
......
34 | forn(i,p.size()) r[i]=p[i];
| ~~~~~~~~~~
gondola.cpp:34:5: note: in expansion of macro 'forn'
34 | forn(i,p.size()) r[i]=p[i];
| ^~~~
gondola.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define forn(i,n) for(int i=0;i<n;++i)
......
58 | forn(i,p.size()) r[i]=p[i];
| ~~~~~~~~~~
gondola.cpp:58:3: note: in expansion of macro 'forn'
58 | forn(i,p.size()) r[i]=p[i];
| ^~~~
/usr/bin/ld: /tmp/ccwTY7kG.o: in function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
collect2: error: ld returned 1 exit status
