| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 818145 | andecaandeci | Gondola (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX=25e4;
int valid(int n, int a[]) {
int next=-1, ret=0;
vector<bool> occ(MAX+1);
for(int i=0; i<n; i++) {
if(occ[a[i]]) return 0;
occ[a[i]]=1;
if(next!=-1) next=next%n+1;
if(a[i]<=0) return 0;
if(a[i]<=n) {
if(next==-1) next=a[i];
if(a[i]!=next) return 0;
}
}
return 1;
}
int replacement(int n, int a[], int b[]) {
int idx=0, next=-1;
priority_queue<pair<int, int>> pq;
int init[n];
for(int i=0; i<n; i++) {
if(next!=-1) init[i]=next=next%n+1;
else if(a[i]<=n) init[i]=next=a[i];
}
if(next==-1) next=n;
for(int i=0; i<n; i++) init[i]=next=next%n+1;
for(int i=0; i<n; i++)
if(a[i]>n) pq.push({-a[i], init[i]});
next=n+1;
while(!pq.empty()) {
int u=pq.top().first, v=pq.top().second;
u=-u; b[idx++]=v;
while(next<u) b[idx++]=next++;
next++;
pq.pop();
}
return idx;
}
const int MOD=1e9+9;
int binpow(int b, int exp) {
long long base=b, ret=1;
while(exp) {
if(exp&1) ret=ret*base%MOD;
base=base*base%MOD;
exp>>=1;
}
return ret;
}
int countReplacement(int n, int a[]) {
if(!valid(n, a)) return 0;
long long ans=1;
int las=n+1, cnt=0;
priority_queue<int> pq;
for(int i=0; i<n; i++)
if(a[i]>n) pq.push(-a[i]), cnt++;
while(!pq.empty()) {
int u=-pq.top(); pq.pop();
ans=ans*binpow(cnt, u-las)%MOD;
las=u+1;
cnt--;
}
bool nperm=0;
for(int i=0; i<n; i++) if(a[i]<=n) nperm=1;
return (nperm ? 1 : n)*ans%MOD;
}
int main() {
int n; cin >> n;
int a[n]; for(int i=0; i<n; i++) cin >> a[i];
cout << countReplacement(n, a) << endl;
}