Submission #311677

#TimeUsernameProblemLanguageResultExecution timeMemory
311677tfgComparing Plants (IOI20_plants)C++17
44 / 100
3018 ms12292 KiB
#include "plants.h" #include <vector> #include <queue> #include <cassert> #include <iostream> const int INF = 1e9; struct SegTree { void init(std::vector<int> &a) { n = (int) a.size(); tree.assign(4*n, 0); lazy.assign(4*n, 0); build(1, 0, n, a); } void build(int id, int l, int r, std::vector<int> &a) { if(l + 1 == r) { tree[id] = a[l]; } else { int mid = (l + r) / 2; build(id+id, l, mid, a); build(id+id+1, mid, r, a); tree[id] = std::min(tree[id+id], tree[id+id+1]); } } int qry(int l, int r) { while(l >= n) { l -= n; r -= n; } while(l < 0) { l += n; r += n; } if(r > n) { return std::min(qry(l, n), qry(0, r-n)); } return qry(1, 0, n, l, r); } int qry(int id, int l, int r, int i, int j) { //std::cout << "qry (" << id << ", " << l << ", " << r << ", " << i << ", " << j << ")\n"; if(l >= r || r <= i || l >= j) return INF; if(i <= l && r <= j) return tree[id]; int mid = (l + r) / 2; push(id); return std::min(qry(id+id, l, mid, i, j), qry(id+id+1, mid, r, i, j)); } void upd(int l, int r, int v) { while(l >= n) { l -= n; r -= n; } while(l < 0) { l += n; r += n; } if(r > n) { upd(l, n, v); upd(0, r-n, v); } else { upd(1, 0, n, l, r, v); } } void upd(int id, int l, int r, int i, int j, int v) { if(l >= r || r <= i || l >= j) return; if(i <= l && r <= j) { tree[id] += v; lazy[id] += v; return; } int mid = (l + r) / 2; push(id); upd(id+id, l, mid, i, j, v); upd(id+id+1, mid, r, i, j, v); tree[id] = std::min(tree[id+id], tree[id+id+1]); } void push(int id) { if(lazy[id]) { //assert(id+id+1 < 4*n); lazy[id+id] += lazy[id]; lazy[id+id+1] += lazy[id]; tree[id+id] += lazy[id]; tree[id+id+1] += lazy[id]; lazy[id] = 0; } } int n; std::vector<int> tree, lazy; }; const int me = 18; const int ms = 1 << me; SegTree tree; int pos[me][2][ms]; int leftmost(int l, int r) { if(l+1 >= r) return l; int mid = l + (r - l) / 2; if(tree.qry(l, mid) == 0) return leftmost(l, mid); else return leftmost(mid, r); } int rightmost(int l, int r) { if(l+1 >= r) return l; int mid = l + (r - l) / 2; if(tree.qry(mid, r) == 0) return rightmost(mid, r); else return rightmost(l, mid); } bool test(int i, int k) { return tree.qry(i, i+1) == 0 && tree.qry(i-k+1, i) != 0; } template<const int rep> void solve(std::vector<int> r, int k, int bit, int ans[ms]) { int n = (int) r.size(); std::priority_queue<std::pair<int, int>> hp; tree.init(r); std::vector<bool> kek(n, false); for(int i = 0; i < n; i++) { if(test(i, k)) { kek[i] = true; hp.push({(((i >> bit) & 1) ^ rep) * 1001000 + (rep == 0 ? i : -i), i}); } } int id = 0; while(!hp.empty() && id != n) { int on = hp.top().second; hp.pop(); tree.upd(on, on+1, INF); assert(tree.qry(on-k+1, on) != 0); tree.upd(on-k+1, on, -1); int l1 = leftmost(on-k+1, on); int l2 = leftmost(on+1, on+k); l1 = (l1 % n + n) % n; l2 = (l2 % n + n) % n; if(!kek[l1] && test(l1, k)) { kek[l1] = true; hp.push({(((l1 >> bit) & 1) ^ rep) * 1001000 + (rep == 0 ? l1 : -l1), l1}); } if(!kek[l2] && test(l2, k)) { kek[l2] = true; hp.push({(((l2 >> bit) & 1) ^ rep) * 1001000 + (rep == 0 ? l2 : -l2), l2}); } ans[on] = id++; } assert(id == n); } void init(int k, std::vector<int> r) { for(int bit = 0; bit < 1; bit++) { //std::cout << "solving for bit " << bit << std::endl; solve<0>(r, k, bit, pos[bit][0]); //solve<1>(r, k, bit, pos[bit][1]); } return; } int getAnswer(int x, int y, int bit) { int b1 = pos[bit][0][x] < pos[bit][0][y]; //int b2 = pos[bit][1][x] < pos[bit][1][y]; int b2 = b1; int wot = b1 + 2 * b2; if(wot == 3) { return 1; } else if(wot == 0) { return -1; } else { return 0; } } int getBit(int x) { return (x & 1) ? 0 : 1 + getBit(x / 2); } int compare_plants(int x, int y) { return getAnswer(x, y, 0); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...