Submission #573916

#TimeUsernameProblemLanguageResultExecution timeMemory
573916lumibonsFlight to the Ford (BOI22_communication)C++17
26.40 / 100
4809 ms2052 KiB
#include <vector> #include <cstdlib> #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(int n) { vector<vector<interval>> r; ll o = 0, rs = s; for (int i = 0; i < n; i++) { ll cs = rs / (n - i); rs -= cs; r.push_back(splitIntervals(c, o, cs)); o += cs; } 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; } }; void reduce(state &s, int ps, const vector<int> &p, int X = -1) { // if (rand() & 1) // X != -1 ? send(0) : receive(); int rp = 0, pc = (int) p.size(); vector<vector<interval>> c = s.split(pc); int sp = 0; while (X != -1 && !contains(c[sp], X)) sp++; for (int i = 0; i < ps; i++) rp |= (X != -1 ? send((p[sp] >> i) & 1) : receive()) << i; vector<vector<interval>> nc; for (int i = 0; i < pc; i++) if (((p[i] ^ rp) & ((p[i] ^ rp) >> 1)) == 0) nc.push_back(c[i]); s = state(nc); } std::pair<int, int> solve(int N, int X = -1) { state s(N); srand(42); // for (int ps = 10; ps >= 4; ps -= 2) { // vector<int> p; // for (int i = 0; i < (1 << ps); i++) // p.push_back(i); // while (s.size() >= (int) p.size()) // reduce(s, ps, p, X); // } // -> 106, ok // int ps = 10; // vector<int> p; // for (int i = 0; i < (1 << ps); i++) // p.push_back(i); // while (s.size() >= (int) p.size()) // reduce(s, ps, p, X); // -> 108, ok while (s.size() >= 6) reduce(s, 5, {0, 3, 12, 17, 10, 31}, X); // -> 224, ok // reduce(s, 4, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, X); // -> 116, ok // reduce(s, 4, {1, 2, 4, 15}, X); // -> >250, ok // reduce(s, 4, {0, 7, 9, 15}, X); // -> >250, ok while (s.size() > 2) reduce(s, 4, {0, 6, 9, 15}, X); 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...