Submission #859116

#TimeUsernameProblemLanguageResultExecution timeMemory
859116vgtcrossFlight to the Ford (BOI22_communication)C++17
0 / 100
241 ms344 KiB
#include <bits/stdc++.h> #define MODE 0 using namespace std; using ll = long long; using pii = pair<int, int>; int send(int s) #if MODE { cout << "send " << s << endl; cin >> s; return s; } #else ; #endif int receive() #if MODE { cout << "receive: " << flush; int s; cin >> s; return s; } #else ; #endif int write(int s) { //cout << "w: " << s << '\n'; if (s == 1) { int p = 0; while (p == 0) p = send(1); return send(1) + 2; } else { int p = 2; while (p--) if (send(0)) return send(3 - s) + 2; return 1; } } const int N = 1e9; void encode(int n, int x) { set<pii> s; s.insert({1, N + 1}); int len = N; while (len > 2) { int mid1 = len / 3; int mid2 = 2 * len / 3; int cum = 0; for (pii p : s) { if (x >= p.second) cum += p.second - p.first; else { cum += x - p.first; break; } } int b; if (cum < mid1) b = write(1); else if (cum < mid2) b = write(2); else b = write(3); //cout << "r: " << b << '\n'; set<pii> l, r, era, ins; int cur = 0; for (pii p : s) { if (cur == mid1) break; if (cur + p.second - p.first <= mid1) { l.insert(p); era.insert(p); cur += p.second - p.first; } else { l.insert({p.first, p.first + mid1 - cur}); ins.insert({p.first + mid1 - cur, p.second}); era.insert(p); cur = mid1; } } for (pii p : era) s.erase(p); era.clear(); ins.clear(); for (pii p : s) { if (cur == mid2) break; if (cur + p.second - p.first <= mid2) { r.insert(p); era.insert(p); cur += p.second - p.first; } else { r.insert({p.first, p.first + mid2 - cur}); ins.insert({p.first + mid2 - cur, p.second}); era.insert(p); cur = mid2; } } for (pii p : era) s.erase(p); for (pii p : ins) s.insert(p); era.clear(); ins.clear(); if (b == 1) { for (pii p : r) s.insert(p); len -= mid1; } else if (b == 2) { for (pii p : l) s.insert(p); len -= mid2 - mid1; } else { for (pii p : r) l.insert(p); swap(l, s); len -= len - mid2; } } } int read() { if (receive()) return receive() + 2; if (receive()) return receive() + 2; return 1; } pair<int, int> decode(int n) { set<pii> s; s.insert({1, N + 1}); int len = N; while (len > 2) { int mid1 = len / 3; int mid2 = 2 * len / 3; int b = read(); set<pii> l, r, era, ins; int cur = 0; for (pii p : s) { if (cur == mid1) break; if (cur + p.second - p.first <= mid1) { l.insert(p); era.insert(p); cur += p.second - p.first; } else { l.insert({p.first, p.first + mid1 - cur}); ins.insert({p.first + mid1 - cur, p.second}); era.insert(p); cur = mid1; } } for (pii p : era) s.erase(p); era.clear(); ins.clear(); for (pii p : s) { if (cur == mid2) break; if (cur + p.second - p.first <= mid2) { r.insert(p); era.insert(p); cur += p.second - p.first; } else { r.insert({p.first, p.first + mid2 - cur}); ins.insert({p.first + mid2 - cur, p.second}); era.insert(p); cur = mid2; } } for (pii p : era) s.erase(p); for (pii p : ins) s.insert(p); era.clear(); ins.clear(); if (b == 1) { for (pii p : r) s.insert(p); len -= mid1; } else if (b == 2) { for (pii p : l) s.insert(p); len -= mid2 - mid1; } else { for (pii p : r) l.insert(p); swap(l, s); len -= len - mid2; } } if (s.size() == 1) return {s.begin()->first, s.begin()->first+1}; else { pii p; auto it = s.begin(); p.first = it->first; ++it; p.second = it->first; return p; } } #if MODE int main() { cin.tie(0) -> sync_with_stdio(0); int n, x; cin >> n >> x; encode(n, x); cout << "\n\nmode swich\n\n\n"; pair<int, int> p = decode(n); cout << "! " << p.first << ' ' << p.second << endl; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...