| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379826 | 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
using namespace std;
const long long MOD = 1e9 + 9; // remember to long long
long long bigmod(long long b,long long p){
if(p==0) return 1;
long long r=bigmod(b,p/2);
if(p&1) return (((r*r)%MOD)*b)%MOD;
return (r*r)%MOD;
}
int valid(int n,int inputSeq[]){
long long cnt=0;
set<long long>s;
for(long long i=0;i<n;i++) s.insert(inputSeq[i]);
for(long long i=0;i<n;i++)cnt+=(inputSeq[i]>=1&&inputSeq[i]<=n);
if(s.size()!=n) return 0;
if(cnt==0) return 1;
for(long long i=0;i<n;i++){
if(inputSeq[i]>=1 && inputSeq[i]<=n){
long long now=inputSeq[i];
for(long long 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[]){
long long cnt=0, maxel=0;
for(long long i=0;i<n;i++){
cnt+=(gondolaSeq[i]>=1 && gondolaSeq[i]<=n);
maxel=max(maxel,gondolaSeq[i]);
}
long long l=maxel-n;
if(cnt==0){
pair<long long,long long>gs[n];
for(long long i=0;i<n;i++) gs[i]={gondolaSeq[i],i};
sort(gs,gs+n);
long long now=0, ok=n+1;
long long cur[n];
for(long long i=0;i<n;i++)cur[i]=i+1;
for(long long 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<long long,long long> >v;
for(long long i=0;i<n;i++){
if(gondolaSeq[i]>n) v.pb({gondolaSeq[i],i});
}
sort(v.begin(),v.end());
long long V=v.size();
long long now=0, ok=n+1;
long long cur[n];
for(long long i=0;i<n;i++){
if(gondolaSeq[i]>=1 && gondolaSeq[i]<=n){
long long now=gondolaSeq[i];
for(long long j=i;j<i+n;j++){
cur[j%n]=now;
now=now%n+1;
}
break;
}
}
for(long long 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<long long>all;
for(long long i=0;i<n;i++)all.insert(inputSeq[i]);
long long tar=1;
if(all.size()!=n) return 0;
for(long long 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=1;
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;
}