Submission #1011335

#TimeUsernameProblemLanguageResultExecution timeMemory
1011335parsadox2Last supper (IOI12_supper)C++17
0 / 100
226 ms20192 KiB
#include <bits/stdc++.h> #include "advisor.h" #define F first #define S second using namespace std; const int N = 1e5 + 10; int n , m , k , ar[N] , lg; vector <int> pos[N]; bool marked[N]; struct SEG{ int sum[N << 2]; void Add(int x , int node = 1 , int nl = 0 , int nr = n) { sum[node]++; if(nl + 1 == nr) return; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) Add(x , lc , nl , mid); else Add(x , rc , mid , nr); } void Rem(int x , int node = 1 , int nl = 0 , int nr = n) { sum[node]--; if(nl + 1 == nr) return; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) Rem(x , lc , nl , mid); else Rem(x , rc , mid , nr); } int Get_val(int x , int node = 1 , int nl = 0 , int nr = n) { if(nl + 1 == nr) return nl; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x <= sum[lc]) return Get_val(x , lc , nl , mid); else return Get_val(x - sum[lc] , rc , mid , nr); } int Get_id(int x , int node = 1 , int nl = 0 , int nr = n) { if(nl + 1 == nr) return sum[node]; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) return Get_id(x , lc , nl , mid); else return sum[lc] + Get_id(x , rc , mid , nr); } bool Ex(int x , int node = 1 , int nl = 0 , int nr = n) { if(nl + 1 == nr) return sum[node]; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) return Ex(x , lc , nl , mid); else return Ex(x , rc , mid , nr); } } seg; void Print(int val) { for(int i = 0 ; i < lg ; i++) { if((val >> i) & 1) WriteAdvice(1); else WriteAdvice(0); } } void ComputeAdvice(int *C, int nn, int kk, int mm) { n = nn; k = kk; m = mm; lg = 1; int tmp = 2; while(tmp < k) { lg++; tmp *= 2; } for(int i = 0 ; i < n ; i++) { ar[i] = C[i]; pos[i].push_back(n + 1); } for(int i = n - 1 ; i > -1 ; i--) { pos[ar[i]].push_back(i); } set <pair<int , int>> st; vector <int> vec; for(int i = 0 ; i < k ; i++) { seg.Add(i); st.insert(make_pair(pos[i].back() , i)); } for(int i = 0 ; i < k ; i++) { if(pos[i].size() == 1) { marked[i] = true; vec.push_back(i); WriteAdvice(1); } else WriteAdvice(0); } for(int i = k ; i < n ; i++) { if(pos[i].size() == 2) { marked[i] = true; WriteAdvice(1); } else WriteAdvice(0); } for(int i = 0 ; i < n ; i++) { if(!seg.Ex(ar[i])) { pos[ar[i]].pop_back(); auto it = st.end(); it--; auto now = *it; if(!vec.empty()) { now = make_pair(n + 1 , vec.back()); vec.pop_back(); st.erase(now); seg.Rem(now.S); seg.Add(ar[i]); st.insert(make_pair(pos[ar[i]].back() , ar[i])); if(marked[ar[i]]) vec.push_back(ar[i]); continue; } st.erase(now); int id_rem = seg.Get_id(now.S); id_rem--; seg.Rem(now.S); seg.Add(ar[i]); st.insert(make_pair(pos[ar[i]].back() , ar[i])); Print(id_rem); } else { st.erase(make_pair(pos[ar[i]].back() , ar[i])); pos[ar[i]].pop_back(); st.insert(make_pair(pos[ar[i]].back() , ar[i])); } } } //
#include <bits/stdc++.h> #include "assistant.h" #define F first #define S second using namespace std; const int N = 1e5 + 10; int n2 , k2 , r2 , lg2; struct SEG{ int sum[N << 2]; void Add(int x , int node = 1 , int nl = 0 , int nr = n2) { sum[node]++; if(nl + 1 == nr) return; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) Add(x , lc , nl , mid); else Add(x , rc , mid , nr); } void Rem(int x , int node = 1 , int nl = 0 , int nr = n2) { sum[node]--; if(nl + 1 == nr) return; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) Rem(x , lc , nl , mid); else Rem(x , rc , mid , nr); } int Get_val(int x , int node = 1 , int nl = 0 , int nr = n2) { if(nl + 1 == nr) return nl; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x <= sum[lc]) return Get_val(x , lc , nl , mid); else return Get_val(x - sum[lc] , rc , mid , nr); } int Get_id(int x , int node = 1 , int nl = 0 , int nr = n2) { if(nl + 1 == nr) return sum[node]; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) return Get_id(x , lc , nl , mid); else return sum[lc] + Get_id(x , rc , mid , nr); } bool Ex(int x , int node = 1 , int nl = 0 , int nr = n2) { if(nl + 1 == nr) return sum[node]; int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1; if(x < mid) return Ex(x , lc , nl , mid); else return Ex(x , rc , mid , nr); } } seg2; void Assist(unsigned char *ar, int nn, int kk, int rr) { n2 = nn; k2 = kk; r2 = rr; lg2 = 1; int tmp = 2; while(tmp < k2) { lg2++; tmp *= 2; } //cout << lg2 << endl; vector <int> vec; for(int i = 0 ; i < k2 ; i++) { seg2.Add(i); if(ar[i] == 1) vec.push_back(i); } int pos = n2; for(int i = 0 ; i < n2 ; i++) { int now = GetRequest(); if(seg2.Ex(now)) continue; if(!vec.empty()) { int bd = vec.back(); PutBack(bd); seg2.Rem(bd); seg2.Add(now); vec.pop_back(); if(ar[now]) vec.push_back(now); continue; } int id = 0; for(int j = 0 ; j < lg2 ; j++) { if(ar[pos] == 1) { id |= (1 << j); } pos++; } id++; int bd = seg2.Get_val(id); PutBack(bd); seg2.Rem(bd); seg2.Add(now); if(ar[now]) vec.push_back(now); } } //
#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...