Submission #561957

#TimeUsernameProblemLanguageResultExecution timeMemory
561957JesusLast supper (IOI12_supper)C++14
100 / 100
158 ms74216 KiB
#include<bits/stdc++.h> #include "advisor.h" using namespace std; int andamio[100001]; queue<int> rep[100001]; pair<int,int> st[400010]; void st_i(int j,int i=0,int pos=1){ if(i==j){ int aux=andamio[i]; if(rep[aux].size()>0) { aux=rep[aux].front(); } else aux=100001; st[pos]={aux,aux}; return; } st[pos*2]={-1,1000000}; st[pos*2+1]=st[pos*2]; st_i((i+j)/2,i,pos*2); st_i(j,(i+j)/2+1,pos*2+1); st[pos].first=max(st[pos*2].first,st[pos*2+1].first); st[pos].second=min(st[pos*2].second,st[pos*2+1].second); } int act; void st_ap(int j,int i=0,int pos=1){ if(i==j){ int aux=andamio[i]; if(rep[aux].size()>0) aux=rep[aux].front(); else aux=100001; st[pos]={aux,aux}; return; } if(st[pos*2].second==act) st_ap((i+j)/2,i,pos*2); else st_ap(j,(i+j)/2+1,pos*2+1); st[pos].first=max(st[pos*2].first,st[pos*2+1].first); st[pos].second=min(st[pos*2].second,st[pos*2+1].second); } void st_ag(int j,int i=0,int pos=1){ if(i==j){ int aux=andamio[i]; if(rep[aux].size()>0) aux=rep[aux].front(); else aux=100001; st[pos]={aux,aux}; return; } if(st[pos*2].first==act) st_ag((i+j)/2,i,pos*2); else st_ag(j,(i+j)/2+1,pos*2+1); st[pos].first=max(st[pos*2].first,st[pos*2+1].first); st[pos].second=min(st[pos*2].second,st[pos*2+1].second); } int return_min(int j,int i=0,int pos=1){ if(i==j) return i; else if(st[pos].second==st[pos*2].second) return return_min((i+j)/2,i,pos*2); else return return_min(j,(i+j)/2+1,pos*2+1); } int return_max(int j,int i=0,int pos=1){ if(i==j) return i; else if(st[pos].first==st[pos*2].first) return return_max((i+j)/2,i,pos*2); else return return_max(j,(i+j)/2+1,pos*2+1); } char valor[200002]; int ult[100001]; void ComputeAdvice(int *C, int N, int K, int M) { for(int i=0;i<N;i++){ if(i<K) { andamio[i]=i; valor[i]=1; ult[i]=i; } rep[C[i]].push(i); } st_i(K-1); for(int i=0;i<N;i++){ valor[i+K]=1; if(st[1].second==i){ int pos=andamio[return_min(K-1)]; rep[pos].pop(); act=i; st_ap(K-1); ult[pos]=i+K; } else{ int pos=return_max(K-1); valor[ult[andamio[pos]]]=0; rep[C[i]].pop(); andamio[pos]=C[i]; act=st[1].first; st_ag(K-1); ult[C[i]]=i+K; } } for(int i=0;i<N+K;i++){ WriteAdvice(valor[i]); } } /*10 3 200 6 2 2 1 3 6 9 8 6 2*/
#include<bits/stdc++.h> #include "assistant.h" using namespace std; queue<int> lib; int an[100001]; int col[100001]; void Assist(unsigned char *A, int N, int K, int R){ for(int i=0;i<N;i++){ if(i<K){ an[i]=i; col[i]=i; if(A[i]==0) lib.push(i); } else col[i]=-1; } for(int i=0;i<N;i++){ int c=GetRequest(); if(col[c]==-1){ int pos=0; if(lib.size()>0){ pos=lib.front(); lib.pop(); } PutBack(an[pos]); col[an[pos]]=-1; col[c]=pos; an[pos]=c; } if(A[i+K]==0) lib.push(col[c]); } }
#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...