제출 #1192853

#제출 시각아이디문제언어결과실행 시간메모리
1192853NewtonabcGondola (IOI14_gondola)C++20
90 / 100
37 ms8264 KiB
#include "gondola.h" #include<bits/stdc++.h> using namespace std; const long long MOD=1e9+9; const int N=3e5+10; long long cnt[N],a[N],suf[N]; set<long long> change; long long modofpow(long long n,long long p){ long long mult=n,ans=1; while(p){ if(p%2LL==1LL) ans*=mult,ans%=MOD; p/=2LL; mult=mult*mult; mult%=MOD; } return ans; } int valid(int n, int inputSeq[]) { bool v=true; int mn=INT_MAX; int idx=-1; set<int> s; for(int i=0;i<n;i++){ if(s.find(inputSeq[i])!=s.end()) v=false; s.insert(inputSeq[i]); if(inputSeq[i]>n) continue; if(mn>inputSeq[i]){ mn=inputSeq[i]; idx=i; } } int now; if(idx!=-1){ now=inputSeq[idx]; for(int i=idx;i<idx+n;i++,now++){ int con=i%n; if(inputSeq[con]>n) continue; if(inputSeq[con]!=now){ v=false; } } } return v; } //---------------------- int replacement(int n, int gondolaSeq[], int ans[]) { int idx=n; for(int i=0;i<n;i++){ if(gondolaSeq[i]>n) continue; idx=i; break; } int pt=gondolaSeq[idx]; if(idx!=n) for(int i=idx;i<idx+n;i++){ int con=(pt-1)%n+1; a[con]=gondolaSeq[i%n]; pt++; } if(idx==n) for(int i=1;i<=n;i++) a[i]=gondolaSeq[i-1]; for(int i=1;i<=n;i++){ if(a[i]<=n) continue; cnt[a[i]]=i; } int mx=*max_element(a+1,a+n+1); int now=cnt[mx]; for(int i=mx;i>n;i--){ if(cnt[i]==0) cnt[i]=now; if(cnt[i]!=now) now=cnt[i]; } // for(int i=n+1;i<=mx;i++) cout<<cnt[i] <<" "; // cout<<"\n"; int len=mx-n; for(int i=1;i<=n;i++) a[i]=i; for(int i=n+1;i<=mx;i++){ int ansidx=i-n-1; ans[ansidx]=a[cnt[i]]; a[cnt[i]]=i; } return len; } //---------------------- int countReplacement(int n, int gondolaSeq[]) { if(!valid(n,gondolaSeq)) return 0; bool cyc=true; for(int i=0;i<n;i++) if(gondolaSeq[i]<=n) cyc=false; int idx=n; for(int i=0;i<n;i++){ if(gondolaSeq[i]>n) continue; idx=i; break; } int pt=gondolaSeq[idx]; if(idx!=n) for(int i=idx;i<idx+n;i++){ int con=(pt-1)%n+1; a[con]=gondolaSeq[i%n]; pt++; } if(idx==n) for(int i=1;i<=n;i++) a[i]=gondolaSeq[i-1]; int mx=*max_element(a+1,a+n+1); for(int i=n+1;i<=mx;i++) cnt[i]=0; for(int i=1;i<=n;i++){ if(a[i]<=n) continue; change.insert(a[i]); } // for(int i=n+1;i<=mx;i++) cout<<cnt[i] <<" "; // cout<<"\n"; long long ans=1; if(!change.empty()) ans=modofpow((long long)(change.size()),((*change.begin())-((long long)n+1LL))); long long tmp=change.size(); for(auto it=change.begin();it!=change.end();it++){ tmp--; auto nxt=it; nxt++; if(nxt==change.end()) break; ans*=modofpow(tmp,*nxt-*it-1LL); ans%=MOD; } if(cyc) ans*=(long long)n,ans%=MOD; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...