//#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
int valid(int n, int a[])
{
set <int> st;
for (int i = 0; i < n; i++) st.insert(a[i]);
if (st.size() != n) return 0;
vector <pair<int, int>> b;
for (int i = 0; i < n; i++){
if (a[i] <= n) b.push_back({a[i], i});
}
for (int i = 1; i < b.size(); i++){
int need = b[i - 1].first + b[i].second - b[i - 1].second;
if (need > n) need -= n;
if (b[i].first != need) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int a[], int b[])
{
int mx = 0;
for (int i = 0; i < n; i++) mx = max(mx, a[i]);
int mn = 1e6;
int c[n];
for (int i = 0; i < n; i++) mn = min(mn, a[i]);
if (mn > n){
for (int i = 0; i < n; i++) c[i] = i + 1;
} else {
int p = -1;
for (int i = 0; i < n; i++){
if (a[i] <= n) p = i;
}
c[p] = a[p];
for (int i = p + 1; i < n; i++){
c[i] = c[i - 1] + 1;
if (c[i] > n) c[i] = 1;
}
if (p != 0){
c[0] = c[n - 1] + 1;
if (c[0] > n) c[0] = 1;
for (int i = 1; i < p; i++){
c[i] = c[i - 1] + 1;
if (c[i] > n) c[i] = 1;
}
}
}
int l = 0;
set <pair<int, int>> st;
for (int i = 0; i < n; i++){
if (c[i] != a[i]){
st.insert(make_pair(a[i], i));
}
}
int repl = n + 1;
while (st.size()){
auto u = *st.begin();
b[l++] = c[u.second];
c[u.second] = repl++;
if (c[u.second] == a[u.second]) st.erase(u);
}
return l;
}
//----------------------
long long power(long long x, int y){
if (y==0) return 1;
long long v = power(x, y/2);
v *= v; v %= mod;
if (y & 1) return v * x % mod;
else return v;
}
int countReplacement(int n, int a[])
{
if (!valid(n, a)) {
return 0;
}
long long ans = n;
vector <int> v;
for (int i = 0; i < n; i++){
if (a[i] <= n) ans = 1;
else v.push_back(a[i]);
}
sort(v.begin(), v.end());
int choices = v.size();
int curr = n;
for (auto x : v){
int change = x - curr - 1;
ans *= power(choices, change);
ans %= mod;
choices--;
curr = x;
}
return (int)ans;
}
int main(){
int n; cin >> n;
int a[n];
for (int i = 0; i < n; i++) cin >> a[i];
cout << countReplacement(n, a) << "\n";
return 0;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:12:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
12 | if (st.size() != n) return 0;
| ~~~~~~~~~~^~~~
gondola.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 1; i < b.size(); i++){
| ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccqWoIug.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc5ulb9f.o:gondola.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccqWoIug.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
