Submission #836859

#TimeUsernameProblemLanguageResultExecution timeMemory
836859kamelfanger83The Big Prize (IOI17_prize)C++14
20 / 100
27 ms6784 KiB
#include <vector> #include <cassert> #include "prize.h" using namespace std; struct Segtree{ vector<int> cache; Segtree(int n){ cache.resize(4 * n); } void buildao(int l, int r, int i){ cache[i] = r-l; if (l + 1 < r){ int m = l + (r-l)/2; buildao(l, m, i*2+1); buildao(m, r, i*2+2); } } int update(int l, int r, int i, int ui, int ux){ if (ui < l || r <= ui) return cache[i]; if (l + 1 == r) return cache[i] = ux; int m = l + (r-l)/2; return cache[i] = update(l, m, i*2+1, ui, ux) + update(m, r, i*2+2, ui, ux); } int query(int l, int r, int i, int ql, int qr){ if (qr <= l || r <= ql) return 0; if (ql <= l && r <= qr) return cache[i]; int m = l + (r-l)/2; return query(l, m, i*2+1, ql, qr) + query(m, r, i*2+2, ql, qr); } int findi (int l, int r, int i, int sum){ if (l + 1 == r) { if (cache[i] > sum) return l; return r; } int m = l + (r-l)/2; if (cache[i*2+1] > sum) return findi(l, m, i*2+1, sum); else return findi(m, r, i*2+2, sum - cache[i*2+1]); } }; vector<int> queried; int maxsum = 0; Segtree segtree (1); int N; int find(int fake_l, int fake_r, int suml, int sumr, int sumh){ if (fake_l >= fake_r) { assert(sumh == 0); return -1; } int fake_m = (fake_l + fake_r) / 2; int real_m = segtree.findi(0, N, 0, fake_m); auto ans = ask(real_m); int l = ans[0], r = ans[1]; if (l + r == 0) return real_m; else if (l + r > maxsum){ for (int i : queried) segtree.update(0, N, 0, i, 0); queried = {real_m}; maxsum = l + r; return -2; } else if (l + r < maxsum){ segtree.update(0, N, 0, real_m, 0); int middle = 1; for (int dev = 1;; ++dev) { if (fake_m + dev < fake_r) { int real_m = segtree.findi(0, N, 0, fake_m + dev); auto ans = ask(real_m); int l = ans[0], r = ans[1]; if (l + r == 0) return real_m; if (l + r > maxsum) { for (int i : queried) segtree.update(0, N, 0, i, 0); queried = {real_m}; maxsum = l + r; return -2; } if (l + r == maxsum){ int r1 = find(fake_l, fake_m - dev + 1, suml, r + middle, l - suml - middle); int r2 = find(fake_m + dev + 1, fake_r, l, sumr, r - sumr); if (r1 != -1) return r1; return r2; } else { segtree.update(0, N, 0, real_m, 0); } middle++; } if (fake_m - dev >= fake_l) { int real_m = segtree.findi(0, N, 0, fake_m - dev); auto ans = ask(real_m); int l = ans[0], r = ans[1]; if (l + r == 0) return real_m; if (l + r > maxsum) { for (int i : queried) segtree.update(0, N, 0, i, 0); queried = {real_m}; maxsum = l + r; return -2; } if (l + r == maxsum){ int r1 = find(fake_l, fake_m - dev, suml, r, l - suml); int r2 = find(fake_m + dev + 1, fake_r, l + middle, sumr, r - sumr - middle); if (r1 != -1) return r1; return r2; } else { segtree.update(0, N, 0, real_m, 0); } middle++; } else { return -1; } } } int al = l - suml; int ar = r - sumr; if (al > 0){ int ret = find(fake_l, fake_m, suml, r, al); if (ret != -1) return ret; } if (ar > 0){ int ret = find(fake_m - al + 1, fake_r - al, l, sumr, ar); if (ret != -1) return ret; } return -1; } int find_best(int n){ segtree = Segtree (n); N = n; segtree.buildao(0, n, 0); int ret = -2; while (ret == -2){ ret = find(0, segtree.cache[0], 0, 0, -1); } //assert(ret != -1); return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...