Submission #311662

#TimeUsernameProblemLanguageResultExecution timeMemory
311662tfgComparing Plants (IOI20_plants)C++17
0 / 100
4066 ms30496 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(2*n, 0); lazy.assign(2*n, 0); for(int i = 0; i < n; i++) { tree[n+i] = a[i]; } for(int i = n-1; i > 0; i--) { tree[i] = std::min(tree[i+i], tree[i+i+1]); } } void upd(int l, int r, int v) { if(l >= r) { return; } while(l >= n) { l -= n; r -= n; } while(l < 0) { l += n; r += n; } //std::cout << "update [" << l << ", " << r << "), v is " << v << std::endl; if(r > n) { upd(0, r - n, v); r = n; } l += n, r += n; int l0 = l, r0 = r; push(l / 2); push((r-1) / 2); for(; l < r; l /= 2, r /= 2) { if(l & 1) lazy[l++] += v; if(r & 1) lazy[--r] += v; } up(l0); up(r0-1); } int qry(int l, int r) { if(l >= r) return INF; 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)); } //std::cout << "query [" << l << ", " << r << ")" << std::endl; int ans = INF; l += n, r += n; push(l / 2); push((r-1) / 2); for(; l < r; l /= 2, r /= 2) { if(l & 1) ans = std::min(ans, tree[l++]); if(r & 1) ans = std::min(ans, tree[--r]); } //std::cout << "answer is " << ans << '\n'; return ans; } void push(int x) { if(x != 1) push(x / 2); if(x+x < n) { lazy[x+x] += lazy[x]; } if(x+x+1 < n) { lazy[x+x+1] += lazy[x]; } tree[x+x] += lazy[x]; tree[x+x+1] += lazy[x]; lazy[x] = 0; } void up(int x) { if(x >= n) { tree[x] += lazy[x]; lazy[x] = 0; } tree[x/2] = std::min(tree[x], tree[x^1]) + lazy[x/2]; if(x/2 > 1) { up(x/2); } } int n; std::vector<int> tree, lazy; };*/ struct SegTree { void init(std::vector<int> a) { tree = a; n = (int) a.size(); } void upd(int l, int r, int v) { for(int i = l; i < r; i++) { tree[(i%n+n)%n] += v; } } int qry(int l, int r) { int ans = INF; for(int i = l; i < r; i++) { ans = std::min(ans, tree[(i%n+n)%n]); } return ans; } int n; std::vector<int> tree; }; 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; } void solve(std::vector<int> r, int k, int bit, int ans[ms], int rep) { 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)) { //std::cout << "got " << i << std::endl; kek[i] = true; hp.push({((i >> bit) & 1) ^ rep, i}); } } int id = 0; while(!hp.empty()) { int on = hp.top().second; //std::cout << "taking " << on << std::endl; hp.pop(); tree.upd(on, on+1, INF); assert(tree.qry(on-k+1, on) != 0); tree.upd(on-k+1, on, -1); /*for(int i = 0; i < n; i++) { std::cout << tree.qry(i, i+1) << (i + 1 == n ? '\n' : ' '); }*/ int l1 = leftmost(on-k+1, on); int l2 = leftmost(on+1, on+k); l1 = (l1 % n + n) % n; l2 = (l2 % n + n) % n; //std::cout << "testing " << l1 << " and " << l2 << '\n'; if(!kek[l1] && test(l1, k)) { //std::cout << "got " << l1 << '\n'; kek[l1] = true; hp.push({((l1 >> bit) & 1) ^ rep, l1}); } if(!kek[l2] && test(l2, k)) { //std::cout << "got " << l2 << '\n'; kek[l2] = true; hp.push({((l2 >> bit) & 1) ^ rep, l2}); } ans[on] = id++; } assert(id == n); } void init(int k, std::vector<int> r) { for(int bit = 0; bit < me; bit++) { //std::cout << "solving for bit " << bit << std::endl; for(int rep = 0; rep < 2; rep++) { solve(r, k, bit, pos[bit][rep], rep); } } 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 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, getBit(x^y)); }
#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...