| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 781942 | I_Love_EliskaM_ | Gondola (IOI14_gondola) | C++14 | 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;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
const int inf=1e9;
const int mod=1e9+9;
int replacement(int n, int a[], int r[]) {
int m=inf;
forn(i,n) m=min(m,a[i]);
if (m>n) {
vector<int> p;
set<int> s;
forn(i,n) s.insert(i);
map<int,int> mp;
forn(i,n) mp[a[i]]=i;
int l=0; forn(i,n) l=max(l,a[i]);
vector<int> v(n); forn(i,n) v[i]=i+1;
for (int i=n+1; i<=l; ++i) {
if (mp.count(i)) {
p.pb(v[mp[i]]);
s.erase(mp[i]);
} else {
p.pb(v[*s.begin()]);
v[*s.begin()]=i;
}
}
forn(i,p.size()) r[i]=p[i];
return p.size();
}
vector<int> p;
set<int> s;
forn(i,n) if (a[i]>n) s.insert(i);
map<int,int> mp;
forn(i,n) mp[a[i]]=i;
int l=0; forn(i,n) l=max(l,a[i]);
int z=-1;
forn(i,n) if (a[i]<=n) z=i;
vector<int> v(n);
if (z==-1) forn(i,n) v[i]=i+1;
else forn(i,n) v[i]=((a[z]-1+i-z+n)%n)+1;
for (int i=n+1; i<=l; ++i) {
if (mp.count(i)) {
p.pb(v[mp[i]]);
s.erase(mp[i]);
} else {
p.pb(v[*s.begin()]);
v[*s.begin()]=i;
}
}
forn(i,p.size()) r[i]=p[i];
return p.size();
}
int countReplacement(int n, int a[]) {
#define int ll
set<int> s;
forn(i,n) s.insert(a[i]);
if (s.size()<n) return 0;
int m=inf;
forn(i,n) m=min(m,a[i]);
if (m>n) {
vector<int> v; forn(i,n) v.pb(a[i]);
sort(all(v));
ll ans=1;
int p=0;
int k=n;
for (int i=n+1; i<=v.back(); ++i) {
if (v[p]==i) {
--k; ++p; continue;
}
ans=(1ll*ans*k)%mod;
}
return ans;
}
int i=0;
for(;i<n;++i) if (a[i]<=n) break;
i-=a[i]-1;
if (i<0) i+=n;
vector<int> v;
int z=1;
for (int j=i; j<i+n; ++j) {
if (a[j%n]<=n) z&=a[j%n]==j-i+1;
else v.pb(a[j%n]);
}
if (!z) return 0;
if (!v.size()) return 1;
sort(all(v));
int k=v.size();
ll ans=1;
int p=0;
for (int i=n+1; i<=v.back(); ++i) {
if (v[p]==i) {
--k; ++p; continue;
}
ans=(1ll*ans*k)%mod;
}
return ans;
#undef int
}
int valid(int n, int a[]) {
return !!countReplacement(n,a);
}