| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379829 | ponytail | 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 "bits/stdc++.h"
#include "gondola.h"
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int MOD = 1e9 + 9; // remember to int
int bigmod(int b,int p){
if(p==0) return 1;
int r=bigmod(b,p/2);
if(p&1) return (((r*r)%MOD)*b)%MOD;
return (r*r)%MOD;
}
int fact(int x){
if(x<=1) return 1;
return (x*fact(x-1))%MOD;
}
int valid(int n,int inputSeq[]){
int cnt=0;
set<int>s;
for(int i=0;i<n;i++) s.insert(inputSeq[i]);
for(int i=0;i<n;i++)cnt+=(inputSeq[i]>=1&&inputSeq[i]<=n);
if(s.size()!=n) return 0;
if(cnt==0) return 1;
for(int i=0;i<n;i++){
if(inputSeq[i]>=1 && inputSeq[i]<=n){
int now=inputSeq[i];
for(int j=i;j<i+n;j++){
if(now!=inputSeq[j%n] && inputSeq[j%n]>=1 && inputSeq[j%n]<=n){
return 0;
}
now=now%n+1;
}
return 1;
}
}
}
int replacement(int n,int gondolaSeq[],int replacementSeq[]){
int cnt=0, maxel=0;
for(int i=0;i<n;i++){
cnt+=(gondolaSeq[i]>=1 && gondolaSeq[i]<=n);
maxel=max(maxel,gondolaSeq[i]*1LL);
}
int l=maxel-n;
if(cnt==0){
pair<int,int>gs[n];
for(int i=0;i<n;i++) gs[i]={gondolaSeq[i],i};
sort(gs,gs+n);
int now=0, ok=n+1;
int cur[n];
for(int i=0;i<n;i++)cur[i]=i+1;
for(int i=0;i<n;i++){
for(;ok<=gs[i].fi;ok++){
replacementSeq[now++]=cur[gs[i].se];
cur[gs[i].se]=ok;
}
}
return l;
}
vector<pair<int,int> >v;
for(int i=0;i<n;i++){
if(gondolaSeq[i]>n) v.pb({gondolaSeq[i],i});
}
sort(v.begin(),v.end());
int V=v.size();
int now=0, ok=n+1;
int cur[n];
for(int i=0;i<n;i++){
if(gondolaSeq[i]>=1 && gondolaSeq[i]<=n){
int now=gondolaSeq[i];
for(int j=i;j<i+n;j++){
cur[j%n]=now;
now=now%n+1;
}
break;
}
}
for(int i=0;i<V;i++){
for(;ok<=v[i].fi;ok++){
replacementSeq[now++]=cur[v[i].se];
cur[v[i].se]=ok;
}
}
return l;
}
int chk_special_case(int n,int inputSeq[]){
set<int>all;
for(int i=0;i<n;i++)all.insert(inputSeq[i]);
int tar=1;
if(all.size()!=n) return 0;
for(int x:all){
if(x!=tar) return 0;
tar++;
}
return 1;
}
int countReplacement(int n,int inputSeq[]){
if(!valid(n,inputSeq)){
return 0;
}
if(chk_special_case(n,inputSeq)){
return 1;
}
long long cnt=0;
for(long long i=0;i<n;i++){
cnt+=(inputSeq[i]>=1 && inputSeq[i]<=n);
}
if(cnt==0){
long long ans=fact(n);
sort(inputSeq,inputSeq+n);
long long ok=n+1;
for(long long i=0;i<n;i++){
ans*=bigmod(n-i,inputSeq[i]-ok);
ans%=MOD;
ok=inputSeq[i]+1;
}
return ans;
}
long long ans=1;
long long ok=n+1;
vector<long long>v;
for(long long i=0;i<n;i++){
if(inputSeq[i]>n) v.pb(inputSeq[i]);
}
long long V=v.size();
sort(v.begin(), v.end());
for(long long i=0;i<V;i++){
ans*=bigmod(V-i,v[i]-ok);
ans%=MOD;
ok=v[i]+1;
}
return ans;
}