#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define ld long double
const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;
const int mod = 1e9 + 9;
int valid(int n, int inputSeq[]) {
vector<int> a(n);
set<int> lol;
for (int i = 0; i < n; i++) {
a[i] = inputSeq[i];
lol.insert(a[i]);
}
if ((int)lol.size() != n) return 0;
int ind = -1;
for (int i = 0; i < n; i++) {
if (a[i] <= n) ind = i;
}
if (ind == -1) return 1;
int now = a[ind];
for (int i = 0; i < n; i++) {
if (a[ind] <= n && a[ind] != now) return 0;
ind++;
if (ind >= n) ind -= n;
now++;
if (now > n) now = 1;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = gondolaSeq[i];
vector<int> lol;
int ind = -1;
for (int i = 0; i < n; i++) {
if (a[i] > n) lol.pb(a[i]);
else ind = i;
}
vector<int> ans;
sort(all(lol));
map<int, int> ma;
if (ind == -1) {
for (int i = 1; i <= n; i++) {
ma[a[i]] = i;
}
} else {
int now = a[ind];
for (int i = 0; i < n; i++) {
if (a[ind] > n) {
ma[a[ind]] = now;
}
now++;
if (now > n) now = 1;
ind++;
if (ind >= n) ind -= n;
}
}
int last = n;
for (auto &c : lol) {
while (last + 1 <= c) {
ans.pb(ma[c]);
ma[c] = last + 1;
last++;
}
}
int len = ans.size();
for (int i = 0; i < len; i++) replacementSeq[i] = ans[i];
/*
cout << len << endl;
for (auto &c : ans) cout << c << " ";
*/
return len;
}
ll my_pow(ll n, ll m) {
if (m == 0) return 1;
ll now = my_pow(n, m / 2);
if (m % 2 == 0) return (now * now) % mod;
return (((now * now) % mod) * n) % mod;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) return 0;
vector<int> a(n);
bool f = false, is_fixed = false;
vector<int> lol;
ll cnt = n;
for (int i = 0; i < n; i++) {
a[i] = inputSeq[i];
if (a[i] > n) {
f = true;
lol.pb(a[i]);
}
if (a[i] <= n) {
is_fixed = true;
cnt--;
}
}
if (!f) return 1;
sort(all(lol));
ll last = n;
ll ans = 1;
for (int i = 0; i < (int)lol.size(); i++) {
ans *= my_pow(cnt, lol[i] - last - 1);
ans %= mod;
last = lol[i];
cnt--;
}
if (!is_fixed) {
ans *= n;
ans %= mod;
}
return ans;
}
/*
int main() {
int n;
cin >> n;
int a[n], b[n];
for (int i = 0; i < n; i++) cin >> a[i];
replacement(n, a, b);
return 0;
}
*/
Compilation message
/tmp/ccrLCy6T.o: In function `main':
grader.cpp:(.text.startup+0xc3): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0xe2): undefined reference to `valid'
grader.cpp:(.text.startup+0x106): undefined reference to `replacement'
collect2: error: ld returned 1 exit status
