#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
// #include "gondola.h"
using namespace std;
const int N = 1e5 + 10;
int valid(int n,int s[]){
int mn = 2e9;
int ss[n + n + 5] = {0};
map<int,bool> seeen;
for (int i=1;i<=n;i++)
ss[i] = ss[i + n] = s[i-1];
int ind = 0;
for (int i=1;i<=n;i++){
if (ss[i] <= n and ss[i] < mn)
ind = i;
mn = min(mn,ss[i]);
}
for (int i=1;i<=n;i++){
if (seeen[ss[i]])
return false;
seeen[ss[i]] = true;
}
if (mn > n)
return 1;
if (ind < mn)
ind += n;
while (mn>1)
ind--,mn--;
for (int i=ind;mn<=n;mn++,i++)
if (ss[i] != mn and ss[i] <= n)
return 0;
return 1;
}
int replacement(int n,int s[],int sss[]){
int mn = n + 5;
int ss[n + n + 5] = {0};
for (int i=1;i<=n;i++)
ss[i] = ss[i + n] = s[i-1];
map<int,int> seen;
int ind = 0;
int mx = 0;
for (int i=1;i<=n;i++){
if (ss[i] <= n and ss[i] < mn)
mn = min(mn,ss[i]),ind = i;
mx = max(mx,ss[i]);
}
if (ind==0){
int cur = 0;
for (int i=1;i<=n;i++)
seen[ss[i]] = i;
for (int i=n+1;i<=mx;i++){
if (seen[i]==0)
sss[cur++] = seen[mx],seen[mx] = i;
else
sss[cur++] = seen[i];
}
return cur;
}
if (ind < mn)
ind += n;
while (mn>1)
ind--,mn--;
for (int i=ind ; mn<=n ; i++,mn++)
seen[ss[i]] = mn;
//
int cur = 0;
for (int i=n+1;i<=mx;i++){
// cout<<i<<" dd "<<seen[i]<<endl;
if (seen[i]!=0)
sss[cur++] = seen[i];
else
sss[cur++] = seen[mx],seen[mx] = i;
}
return cur;
}
long long power(int a,int b,long long m){
if (b==0)
return 1;
if (b==1)
return a;
long long ans = power(a,b/2,m);
ans = 1LL * ans * ans % m;
if (b%2)
ans = 1LL * a * ans % m;
return ans % mod;
}
int countReplacement(int n,int s[]){
int mn = n + 5;
int ss[n + 5] = {0};
for (int i=1;i<=n;i++)
ss[i] = s[i-1];
int ind = 0;
int mx = 0;
for (int i=1;i<=n;i++)
mx = max(mx,ss[i]);
if (!valid(n,s))
return 0;
if (mx == n)
return 1;
vector<int> v;
for (int i=1;i<=n;i++)
if (ss[i] > n)
v.push_back(ss[i]);
v.push_back(n);
sort(begin(v),end(v));
int sz = v.size();
long long ans = 1;
long long mod = 1000000009;
for (int i=1;i<sz;i++){
int msng = v[i] - v[i-1] - 1;
int rem = sz - i;
ans = 1LL * ans * power(rem,msng,mod) % mod;
}
return ans % mod;
}
Compilation message
gondola.cpp: In function 'long long int power(int, int, long long int)':
gondola.cpp:110:15: error: 'mod' was not declared in this scope
110 | return ans % mod;
| ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:115:6: warning: unused variable 'mn' [-Wunused-variable]
115 | int mn = n + 5;
| ^~
gondola.cpp:121:6: warning: unused variable 'ind' [-Wunused-variable]
121 | int ind = 0;
| ^~~
