Submission #817656

#TimeUsernameProblemLanguageResultExecution timeMemory
817656hugo_pmComparing Plants (IOI20_plants)C++17
55 / 100
310 ms17848 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define rep(i, a, b) for(int i = (a); i < (b); i++) #define sz(v) ((int)((v).size())) template<typename T> void chmax(T &x, const T &v) { if (x < v) x = v; } template<typename T> void chmin(T &x, const T &v) { if (x > v) x = v; } using pii = pair<int, int>; using vi = vector<int>; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif const int INF = 1e9; struct MinAdd { inline int op(int a, int b) { return min(a, b); } const int e = INF; int N; vector<int> tree, lazy; void init(vector<int> v) { N = 1; while (N < (int)v.size()) N <<= 1; tree.assign(2*N, e); lazy.assign(2*N, 0); for (int i = 0; i < (int)v.size(); ++i) { tree[N+i] = v[i]; } for (int i = N-1; i >= 1; --i) { tree[i] = op(tree[2*i], tree[2*i+1]); } } void push(int node) { tree[node] += lazy[node]; if (node < N) { lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node]; } lazy[node] = 0; } void _add(int lq, int rq, int delta) { auto F = [&] (auto f, int node, int lno, int rno) -> void { push(node); if (lq <= lno && rno <= rq) { lazy[node] += delta; push(node); } else if (lno <= rq && lq <= rno) { int mid = (lno+rno)/2; f(f, 2*node, lno, mid); f(f, 2*node+1, mid+1, rno); tree[node] = op(tree[2*node], tree[2*node+1]); } }; F(F, 1, 0, N-1); } optional<int> _popZero(int lq, int rq) { optional<int> ret = nullopt; auto F = [&] (auto f, int node, int lno, int rno) { push(node); if (ret || tree[node] > 0 || rno < lq || rq < lno) { return; } else if (node >= N) { tree[node] = e; ret = node - N; } else { int mid = (lno+rno)/2; f(f, 2*node, lno, mid); f(f, 2*node+1, mid+1, rno); tree[node] = op(tree[2*node], tree[2*node+1]); } }; F(F, 1, 0, N-1); return ret; } optional<int> circleGet(int L, int R) { if (L > R) { auto a = _popZero(L, N-1); return (a ? a : _popZero(0, R)); } return _popZero(L, R); } void circleDecr(int L, int R) { if (L > R) { _add(L, N-1, -1); _add(0, R, -1); } else { _add(L, R, -1); } } }; MinAdd util; int N, K; int add(int x, int y) { x += y; if (x >= N) x -= N; return x; } int sub(int x, int y) { x -= y; if (x < 0) x += N; return x; } int dist(int x, int y) { return min(sub(x,y), sub(y,x)); } vector<int> relative, height; int insertHeight; const int MAX_GRAPH = 300; bool graph[MAX_GRAPH][MAX_GRAPH]; bool pop(int L, int R) { optional<int> ret = util.circleGet(L, R); if (!ret) return false; for (; ret; ret = util.circleGet(L, R)) { int cur = *ret; pop(sub(cur,K-1), sub(cur, 1)); height[cur] = insertHeight--; util.circleDecr(sub(cur,K-1), sub(cur,1)); } return true; } void init(int _k, std::vector<int> _r) { K = _k; relative = _r; N = _r.size(); //-- util.init(relative); height.assign(N, -1); insertHeight = N-1; while(pop(0, N-1)); dbg(height); if (N <= MAX_GRAPH) { rep(i, 0, N) rep(j, 0, N) { graph[i][j] = (dist(i,j) < K && height[i] > height[j]); } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) { graph[i][j] |= (graph[i][k] && graph[k][j]); } } } int compare_plants(int x, int y) { int xy = (height[x] > height[y]); int yx = (height[y] > height[x]); if (N <= MAX_GRAPH) { xy = graph[x][y], yx = graph[y][x]; } return xy - yx; }
#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...