Submission #573906

#TimeUsernameProblemLanguageResultExecution timeMemory
573906lumibonsFlight to the Ford (BOI22_communication)C++17
30 / 100
7812 ms2024 KiB
#include <vector> #include "communication.h" typedef long long ll; using namespace std; struct interval { ll l, r; interval(ll l, ll r) : l(l), r(r) {} bool contains(ll x) { return l <= x && x < r; } ll length() { return r - l; } interval shrink(ll o, ll s) { return interval(min(r, l + o), min(r, l + o + s)); } }; vector<interval> splitIntervals(vector<interval> c, ll o, ll s) { vector<interval> r; for (interval &it : c) { if (s > 0 && it.length() - o > 0) r.push_back(it.shrink(o, s)); s -= max(0LL, min(s, it.length() - o)); o -= min(o, it.length()); } return r; } bool contains(vector<interval> c, ll x) { for (interval &it : c) if (it.contains(x)) return true; return false; } struct state { ll s = 0; vector<interval> c; state() {} state(ll N): s(N) { c.emplace_back(1, N + 1); } state(vector<vector<interval>> &cs) { for (vector<interval> &c : cs) add(c); } void add(interval it) { s += it.length(); c.push_back(it); } void add(vector<interval> &c) { for (interval &it : c) add(it); } vector<vector<interval>> split() { vector<vector<interval>> r; ll s1 = s / 3, s2 = (s - s1) / 2, s3 = s - s1 - s2; r.push_back(splitIntervals(c, 0, s1)); r.push_back(splitIntervals(c, s1, s2)); r.push_back(splitIntervals(c, s1 + s2, s3)); return r; } ll size() { return s; } vector<ll> remaining() { vector<ll> r; for (interval &it : c) for (ll v = it.l; v < it.r; v++) r.push_back(v); return r; } }; std::pair<int, int> solve(int N, int X = -1) { state s(N); while (s.size() > 2) { vector<vector<interval>> c = s.split(); int b1, b2, b3, b4; if (X != -1) { int q1 = contains(c[0], X), q2 = q1 || contains(c[1], X); b1 = send(q1), b2 = send(q2), b3 = send(q2), b4 = send(q1); } else b1 = receive(), b2 = receive(), b3 = receive(), b4 = receive(); c.erase(c.begin() + (b2 == b3 ? (b2 ? 2 : 1) : ((b2 ? b4 : b1) ? 1 : 0))); s = state(c); } vector<ll> r = s.remaining(); return {r[0], r.back()}; } void encode(int N, int X) { solve(N, X); } std::pair<int, int> decode(int N) { return solve(N); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...