Submission #103784

#TimeUsernameProblemLanguageResultExecution timeMemory
103784alexpetrescuLast supper (IOI12_supper)C++14
100 / 100
120 ms7164 KiB
#include "advisor.h" #include <vector> #define MAXN 100009 int heap[MAXN], poz[MAXN], d[MAXN]; inline void mySwap(int p, int q) { int aux = heap[p]; heap[p] = heap[q]; heap[q] = aux; poz[heap[p]] = p; poz[heap[q]] = q; } inline void urcare(int p) { while (p > 1 && d[heap[p]] > d[heap[p / 2]]) { mySwap(p, p / 2); p /= 2; } } inline void coborare(int p) { int q; bool f = 1; while (f && (q = 2 * p) <= heap[0]) { if (q < heap[0] && d[heap[q + 1]] > d[heap[q]]) q++; if (d[heap[q]] > d[heap[p]]) { mySwap(p, q); p = q; } else f = 0; } } void ComputeAdvice(int *C, int N, int K, int M) { std::vector < int > urm(N), last(N, N); for (int i = N - 1; i >= 0; i--) { urm[i] = last[C[i]]; last[C[i]] = i; } for (int i = 0; i < K; i++) d[i] = last[i]; for (int i = 0; i < K; i++) heap[++heap[0]] = i, poz[i] = i + 1; for (int i = heap[0]; i > 0; i--) coborare(i); std::vector < bool > ans(N + K, 1); std::vector < int > moment(N, -1); for (int i = 0; i < K; i++) moment[i] = i; for (int i = 0; i < N; i++) { if (poz[C[i]]) { d[C[i]] = urm[i]; urcare(poz[C[i]]); } else { ans[moment[heap[1]]] = 0; poz[heap[1]] = 0; heap[1] = C[i]; poz[C[i]] = 1; d[heap[1]] = urm[i]; coborare(1); } moment[C[i]] = i + K; } for (int i = 0; i < N + K; i++) WriteAdvice(ans[i]); }
#include "assistant.h" #include <vector> #include <set> std::set < int > s; void Assist(unsigned char *A, int N, int K, int R) { std::vector < int > v(K), t(N, 0); for (int i = 0; i < K; i++) v[i] = i, t[i] = A[i]; for (int i = 0; i < K; i++) if (t[i] == 0) s.insert(i); std::vector < int > avem(N, 0); for (int i = 0; i < K; i++) avem[i] = 1; for (int i = 0; i < N; i++) { int x = GetRequest(); if (!avem[x]) { int y = *(s.begin()); PutBack(y); s.erase(s.begin()); avem[y] = 0; avem[x] = 1; t[x] = A[i + K]; if (t[x] == 0) s.insert(x); } else { if (t[x] == 1 && A[i + K] == 0) s.insert(x); else if (t[x] == 0 && A[i + K] == 1) s.erase(s.lower_bound(x)); t[x] = A[i + K]; } } }
#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...