Submission #365021

#TimeUsernameProblemLanguageResultExecution timeMemory
365021qwerasdfzxclLast supper (IOI12_supper)C++14
100 / 100
136 ms12848 KiB
#include "advisor.h" #include <bits/stdc++.h> using namespace std; vector<int> idx[100100]; int pt[100100], btpos[50050], bg[50050], bt[200200], bgidx[100100]; int tree[200200]; void ComputeAdvice(int *C, int N, int K, int M); void WriteAdvice(unsigned char a); int mx(int a, int b){ if (idx[bg[a]][pt[bg[a]]]>idx[bg[b]][pt[bg[b]]]) return a; return b; } void build(int k){ for (int i=k;i<2*k;i++) tree[i]=i-k; for (int i=k-1;i>0;i--) tree[i]=mx(tree[i<<1], tree[i<<1|1]); } void update(int p, int k){ for (p += k;p>1;p>>=1) tree[p>>1]=mx(tree[p], tree[p^1]); } void ComputeAdvice(int *C, int N, int K, int M){ for (int i=0;i<N;i++){ idx[C[i]].push_back(i); } for (int i=0;i<N;i++) idx[i].push_back(1e9); for (int i=0;i<N;i++){ bgidx[i]=-1; } for (int i=0;i<K;i++){ bg[i]=i; bgidx[i]=i; btpos[i]=i; } build(K); for (int i=0;i<N;i++){ if (bgidx[C[i]]!=-1){ int tmp=bgidx[C[i]]; bt[btpos[tmp]]=0; btpos[tmp]=K+i; pt[C[i]]++; update(tmp, K); } else{ int tmp=tree[1]; bt[btpos[tmp]]=1; btpos[tmp]=K+i; pt[C[i]]++; bgidx[bg[tmp]]=-1; bgidx[C[i]]=tmp; bg[tmp]=C[i]; update(tmp, K); } } for (int i=0;i<N+K;i++){ if (bt[i]==0) WriteAdvice(0); else WriteAdvice(1); } } /*#include "assistant.h" #include <bits/stdc++.h> using namespace std; queue<int> q; int bg[100100]; int bgyes[100100]; void Assist(unsigned char *A, int N, int K, int R); void PutBack(int T); int GetRequest(); void Assist(unsigned char *A, int N, int K, int R){ fill(bgyes, bgyes+N, -1); for (int i=0;i<K;i++){ if (A[i]) q.push(i); bgyes[i]=i; bg[i]=i; } for (int i=0;i<N;i++){ int tmp=GetRequest(); if (bgyes[tmp]!=-1){ if(A[K+i]) q.push(bgyes[tmp]); continue; } int idx=q.front(); q.pop(); PutBack(bg[idx]); bgyes[bg[idx]]=-1; bgyes[tmp]=idx; bg[idx]=tmp; if (A[K+i]) q.push(bgyes[tmp]); } }*/ /*int main(){ int c[100100]={0}; int n, k; scanf("%d %d", &n, &k); for (int i=0;i<n;i++) scanf("%d", c+i); ComputeAdvice(c, n, k, 1000100); } void WriteAdvice(unsigned char a){ if (a) printf("1 "); else printf("0 "); } */ /* int main(){ unsigned char a[200200]; int n, k, r; scanf("%d %d %d", &n, &k, &r); for (int i=0;i<r;i++){ int tmp; scanf("%d", &tmp); if (tmp==0) a[i]=0; else a[i]=1; } Assist(a, n, k, r); } int timer=0, x[4]={2, 0, 3, 0}; int GetRequest(){ timer++; return x[timer-1]; } void PutBack(int abc){ printf("%d ", abc); } */
/*#include "advisor.h" #include <bits/stdc++.h> using namespace std; vector<int> idx[100100]; int pt[100100], btpos[50050], bg[50050], bt[200200], bgidx[100100]; int tree[200200]; void ComputeAdvice(int *C, int N, int K, int M); void WriteAdvice(unsigned char a); int mx(int a, int b){ if (idx[bg[a]][pt[bg[a]]]>idx[bg[b]][pt[bg[b]]]) return a; return b; } void build(int k){ for (int i=k;i<2*k;i++) tree[i]=i-k; for (int i=k-1;i>0;i--) tree[i]=mx(tree[i<<1], tree[i<<1|1]); } void update(int p, int k){ for (p += k;p>1;p>>=1) tree[p>>1]=mx(tree[p], tree[p^1]); } void ComputeAdvice(int *C, int N, int K, int M){ for (int i=0;i<N;i++){ idx[C[i]].push_back(i); } for (int i=0;i<N;i++) idx[i].push_back(1e9); for (int i=0;i<N;i++){ bgidx[i]=-1; } for (int i=0;i<K;i++){ bg[i]=i; bgidx[i]=i; btpos[i]=i; } build(K); for (int i=0;i<N;i++){ if (bgidx[C[i]]!=-1){ int tmp=bgidx[C[i]]; bt[btpos[tmp]]=0; btpos[tmp]=K+i; pt[C[i]]++; update(tmp, K); } else{ int tmp=tree[1]; bt[btpos[tmp]]=1; btpos[tmp]=K+i; pt[C[i]]++; bgidx[bg[tmp]]=-1; bgidx[C[i]]=tmp; bg[tmp]=C[i]; update(tmp, K); } } for (int i=0;i<N+K;i++){ if (bt[i]==0) WriteAdvice(0); else WriteAdvice(1); } }*/ #include "assistant.h" #include <bits/stdc++.h> using namespace std; queue<int> q; int bg[100100]; int bgyes[100100]; void Assist(unsigned char *A, int N, int K, int R); void PutBack(int T); int GetRequest(); void Assist(unsigned char *A, int N, int K, int R){ fill(bgyes, bgyes+N, -1); for (int i=0;i<K;i++){ if (A[i]) q.push(i); bgyes[i]=i; bg[i]=i; } for (int i=0;i<N;i++){ int tmp=GetRequest(); if (bgyes[tmp]!=-1){ if(A[K+i]) q.push(bgyes[tmp]); continue; } int idx=q.front(); q.pop(); PutBack(bg[idx]); bgyes[bg[idx]]=-1; bgyes[tmp]=idx; bg[idx]=tmp; if (A[K+i]) q.push(bgyes[tmp]); } } /*int main(){ int c[100100]={0}; int n, k; scanf("%d %d", &n, &k); for (int i=0;i<n;i++) scanf("%d", c+i); ComputeAdvice(c, n, k, 1000100); } void WriteAdvice(unsigned char a){ if (a) printf("1 "); else printf("0 "); } */ /* int main(){ unsigned char a[200200]; int n, k, r; scanf("%d %d %d", &n, &k, &r); for (int i=0;i<r;i++){ int tmp; scanf("%d", &tmp); if (tmp==0) a[i]=0; else a[i]=1; } Assist(a, n, k, r); } int timer=0, x[4]={2, 0, 3, 0}; int GetRequest(){ timer++; return x[timer-1]; } void PutBack(int abc){ printf("%d ", abc); } */
#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...