제출 #278108

#제출 시각아이디문제언어결과실행 시간메모리
278108amiratou곤돌라 (IOI14_gondola)C++14
75 / 100
27 ms3800 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)(x.size()) const int MOD =(int)(1e9+9); typedef long long ll; int val[100005],here[250005],p[250005],dp[100005][2]; int valid(int n, int inputSeq[]) { int idx=-1; for (int i = 0; i < n; ++i){ if(here[inputSeq[i]])return 0; here[inputSeq[i]]=1; if(inputSeq[i]<=n)idx=i; } if(idx==-1)return 1; int h=inputSeq[idx]; for (int i = 0; i < n; ++i) val[(idx+i)%n]=((h-1+i)%n)+1; for (int i = 0; i < n; ++i) if(inputSeq[i]<=n && inputSeq[i]!=val[i])return 0; return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { memset(here,-1,sizeof here); int flag=-1; for (int i = 0; i < n; ++i){ if(gondolaSeq[i]<=n)flag=i; else here[gondolaSeq[i]]=i; } priority_queue<int,vector<int>,greater<int> > pq; if(flag!=-1){ int g=gondolaSeq[flag]; for (int i = 0; i < n; ++i){ int r=((g-1+i)%n)+1; if(gondolaSeq[(flag+i)%n]!=r)pq.push(gondolaSeq[(flag+i)%n]),p[gondolaSeq[(flag+i)%n]]=r; } } else{ for (int i = 0; i < n; ++i) p[gondolaSeq[i]]=i+1,pq.push(gondolaSeq[i]); } int h=n+1,idx=0; while(!pq.empty()){ int f=pq.top(); pq.pop(); replacementSeq[idx++]=p[f]; while(h<f)replacementSeq[idx++]=h++; h++; } return idx; } //---------------------- int binpow(int a,int b){ if(!b)return 1; ll h=binpow(a,b>>1); h*=h; if(h>=MOD)h%=MOD; if(b&1)h*=a; if(h>=MOD)h%=MOD; return (int)(h); } int countReplacement(int n, int inputSeq[]) { if(!valid(n,inputSeq))return 0; int idx=-1; for (int i = 0; i < n; ++i) if(inputSeq[i]<=n)idx=i; if(idx==-1)return 1; int h=inputSeq[idx]; for (int i = 0; i < n; ++i) val[(idx+i)%n]=((h-1+i)%n)+1; vector<int> vec={n}; for (int i = 0; i < n; ++i) if(inputSeq[i]>n) vec.push_back(inputSeq[i]); ll ans=1; sort(vec.begin(),vec.end()); for (int i = 1; i < sz(vec); ++i) ans=(ans*binpow(sz(vec)-i,vec[i]-vec[i-1]-1))%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...