#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 9;
int valid(int n, int inputSeq[])
{
unordered_set<int> s;
s.reserve(n + 5);
int expected_offset = -1;
for (int i = 0; i < n; i++) {
if (s.find(inputSeq[i]) != s.end()) return 0;
s.insert(inputSeq[i]);
if (inputSeq[i] <= n) {
int offset = (i + 1 - inputSeq[i] + n) % n;
if (expected_offset == -1) {
expected_offset = offset;
} else if (expected_offset != offset) return 0;
}
}
return 1;
}
/*
g++ grader.cpp gondola.cpp -o o
1
30
16 26 18 19 20 13 22 21 24 25 17 27 28 29 30 1 2 3 11 5 6 8 7 9 10 12 4 23 14 15
0
2
6
3 4 5 6 1 2
1
3
7
1 2 3 4 5 6 5
0
*/
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int idx[n + 1];
memset(idx, 0, sizeof idx);
int offset = -1;
for (int i = 0; i <= n - 1; i++) {
if (gondolaSeq[i] <= n) {
offset = (i - gondolaSeq[i] + n + 1) % n;
}
}
for (int i = 0; i < n; i++) {
if (offset == -1) {
idx[i] = i + 1;
continue;
}
idx[i] = (i - offset + n) % n + 1;
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] > n) {
pq.emplace(gondolaSeq[i], idx[i]);
}
}
int l = 0;
int cur = n + 1;
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
replacementSeq[l] = u;
if (cur < w) pq.emplace(w, cur);
l++, cur++;
}
return l;
}
/*
4
2
3 2
1 1
*/
//----------------------
ll modpow(ll a, ll k) {
if (k == 0) return 1;
if (k == 1) return a;
ll tmp = modpow(a, k / 2);
if (k % 2) return (((tmp * tmp) % mod) * a) % mod;
return (tmp * tmp) % mod;
}
int countReplacement(int n, int inputSeq[])
{
ll ans = 1;
if (!valid(n, inputSeq)) return 0;
bool all_in_range = 1;
int offset = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] > n) {
all_in_range = 0;
}
if (inputSeq[i] <= n) {
offset = (i - inputSeq[i] + n + 1) % n;
}
}
if (all_in_range) return 1;
priority_queue<ll, vector<ll>, greater<ll>> pq;
for (int i = 0; i < n; i++) {
if (inputSeq[i] > n) {
pq.emplace(inputSeq[i]);
}
}
ll cur = n + 1;
while (!pq.empty()) {
auto w = pq.top();
ans = (ans * modpow(pq.size(), w - cur)) % mod;
cur = w + 1;
pq.pop();
}
if (offset == -1) return (ans * n) % mod;
return ans;
}
