Submission #988872

#TimeUsernameProblemLanguageResultExecution timeMemory
988872AriadnaLast supper (IOI12_supper)C++14
100 / 100
65 ms9800 KiB
#include "advisor.h" #include <bits/stdc++.h> #define pb push_back using namespace std; struct Segtree { int n; vector<pair<int, int>> st; Segtree(const vector<int>& a) { n = a.size(); st = vector<pair<int, int>>(4*n); build(1, 0, n-1, a); } void build(int p, int l, int r, const vector<int>& a) { if (l == r) st[p] = {a[l], l}; else { int m = (l+r)/2; build(2*p, l, m, a); build(2*p+1, m+1, r, a); if (st[2*p] > st[2*p+1]) st[p] = st[2*p]; else st[p] = st[2*p+1]; } } void change(int p, int l, int r, int i, int v) { if (l == r) st[p] = {v, i}; else { int m = (l+r)/2; if (i <= m) change(2*p, l, m, i, v); else change(2*p+1, m+1, r, i, v); if (st[2*p] > st[2*p+1]) st[p] = st[2*p]; else st[p] = st[2*p+1]; } } pair<int, int> Max(int p, int l, int r, int i, int j) { if (i > j) return {0, -1}; if (i == l && j == r) return st[p]; int m = (l+r)/2; pair<int, int> a = Max(2*p, l, m, i, min(m, j)); pair<int, int> b = Max(2*p+1, m+1, r, max(i, m+1), j); if (a.first > b.first) return a; return b; } void change(int i, int v) { change(1, 0, n-1, i, v); } int idx() { return Max(1, 0, n-1, 0, n-1).second; } }; void ComputeAdvice(int *C, int N, int K, int M) { vector<int> last_pos(N, N); vector<int> next_pos(N); for (int i = N-1; i >= 0; --i) { next_pos[i] = last_pos[C[i]]; last_pos[C[i]] = i; } vector<int> pos_on_scaffold(N, -1); for (int i = 0; i < K; ++i) pos_on_scaffold[i] = i; vector<int> scaffold(K); vector<int> next(K); for (int i = 0; i < K; ++i) { next[i] = last_pos[i]; scaffold[i] = i; } Segtree Scaffold(next); vector<int> take(N); vector<int> optimal_strategy; for (int i = 0; i < N; ++i) { if (pos_on_scaffold[C[i]] != -1) { Scaffold.change(pos_on_scaffold[C[i]], next_pos[i]); take[i] = -1; } else { int idx = Scaffold.idx(); optimal_strategy.pb(idx); Scaffold.change(idx, next_pos[i]); take[i] = scaffold[idx]; pos_on_scaffold[scaffold[idx]] = -1; pos_on_scaffold[C[i]] = idx; scaffold[idx] = C[i]; } } vector<int> time_taken(N, N); vector<int> next_take(N); for (int i = N-1; i >= 0; --i) { next_take[i] = time_taken[C[i]]; if (take[i] != -1) { time_taken[take[i]] = i; } } for (int i = 0; i < K; ++i) { if (time_taken[i] < last_pos[i]) WriteAdvice(1); else WriteAdvice(0); } for (int i = 0; i < N; ++i) { if (next_take[i] < next_pos[i]) WriteAdvice(1); else WriteAdvice(0); } }
#include "assistant.h" #include <bits/stdc++.h> using namespace std; int GetRequest(); void PutBack(int c); void Assist(unsigned char *A, int N, int K, int R) { unordered_set<int> scaffold, can_take; for (int i = 0; i < K; ++i) { scaffold.insert(i); if (A[i] == 1) can_take.insert(i); } for (int i = 0; i < N; ++i) { int c = GetRequest(); if (scaffold.find(c) == scaffold.end()) { scaffold.insert(c); int color = *can_take.begin(); can_take.erase(color); scaffold.erase(color); PutBack(color); } if (A[K+i] == 1) can_take.insert(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...