Submission #872764

#TimeUsernameProblemLanguageResultExecution timeMemory
872764HuyQuang_re_ZeroGondola (IOI14_gondola)C++14
100 / 100
47 ms8020 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define II pair <ll,ll> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define TII pair <treap*,treap*> #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) #define Log(x) (31-__builtin_clz((int)x)) #define LogLL(x) (63-__builtin_clzll((ll)x)) #include "gondola.h" using namespace std; int n,i,a[250005]; int valid(int n,int a[]) { int last_u=0,last_i=0; map <int,int> d; for(i=0;i<n;i++) { int u=a[i]; if(d[u]) return 0; d[u]=1; if(u>n) continue; if(last_u>0 && (u-last_u+n)%n!=(i-last_i+n)%n) return 0; last_u=u; last_i=i; } return 1; } int m,res[250005],pos[250005],last[250005]; int replacement(int n,int a[], int res[]) { int ma=0,m=0; memset(last,-1,sizeof(last)); for(i=0;i<n;i++) ma=max(ma,a[i]),last[a[i]]=i; for(i=1;i<=n;i++) if(last[i]>-1) break; if(i>n) { for(i=0;i<n;i++) a[i]=i+1; } else { // cerr<<i<<" "<<last[i]<<'\n'; int u=i,pos=last[i]; a[pos]=i; for(i=pos+1;i<n;i++) { if(u==n) u=1; else u++; a[i]=u; } u=a[pos]; for(i=pos-1;i>=0;i--) { if(u==1) u=n; else u--; a[i]=u; } } for(i=0;i<n;i++) pos[a[i]]=i; set <int> Replace; for(i=1;i<=n;i++) if(last[i]==-1) Replace.insert(i); for(i=n+1;i<=ma;i++) if(last[i]==-1) { int u=*Replace.begin(); Replace.erase(u); a[pos[u]]=i; pos[i]=pos[u]; Replace.insert(i); res[m++]=u; } else { int u=a[last[i]]; Replace.erase(u); a[pos[u]]=i; pos[i]=pos[u]; res[m++]=u; } return m; } const ll mod=round(1e9)+9; ll lt(ll a,ll b) { if(b==0) return 1; ll tg=lt(a,b/2); return (b%2==0) ? tg*tg%mod : tg*tg%mod*a%mod; } int countReplacement(int n,int a[]) { if(!valid(n,a)) return 0; vector <int> val; for(i=0;i<n;i++) if(a[i]>n) val.push_back(a[i]); int last=n,left=val.size(); ll res=1; if(left==n) res=n; sort(val.begin(),val.end()); for(int x:val) { res=res*lt(left,x-last-1)%mod; last=x; left--; } return res; } /* int main() { freopen("gondola.inp","r",stdin); freopen("gondola.out","w",stdout); cin>>n; for(i=0;i<n;i++) cin>>a[i]; cout<<countReplacement(n,a); } */
#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...