Submission #579855

#TimeUsernameProblemLanguageResultExecution timeMemory
579855balbitFlight to the Ford (BOI22_communication)C++17
74 / 100
3733 ms1948 KiB
#include <bits/stdc++.h> #ifndef BALBIT #include "communication.h" #endif // BALBIT using namespace std; #define ll long long #define pii pair<int, int> #define f first #define s second #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(), (x).end() #define pb push_back #define MX(a,b) a=max(a,b) #define MN(a,b) a = min(a,b) #define FOR(i,a,b) for (int i = a; i<b; ++i) #define REP(i,n) FOR(i,0,n) #define REP1(i,n) FOR(i,1,n+1) #ifdef BALBIT #define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__) template<typename T> void _do( T && x) {cerr<<x<<endl;} template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);} #else #define bug(...) #define endl '\n' #endif // BALBIT int lst[] = {0b0000, 0b0110, 0b1001, 0b1111}; int which[1<<4]; vector<int> chg; void build(){ chg.clear(); REP(ty, (1<<4)) { bool ok = 1; REP(j,3) { if ((ty & (1<<j)) && (ty & (1<<(j+1)))) { ok = 0; } } if (ok) chg.pb(ty); } memset(which, -1, sizeof which); REP(i,4) { which[lst[i]] = i; } } #ifdef BALBIT queue<int> rar; bool canflip = 1; int send(int x){ if (canflip && rand()%2) { rar.push(x^1); canflip = 0; }else{ rar.push(x); canflip = 1; } bug(rar.back()); return rar.back(); } int receive() { int re = rar.front(); rar.pop(); return re; //rar.pop(); } #endif // BALBIT set<vector<int> > st; pii who(int x) { vector<int> re; for (int m : chg) { if (which[m^x] != -1) { re.pb(which[m^x]); } } assert(SZ(re) <= 2); sort(ALL(re)); // st.insert(re); return {re[0], re[1]}; // bug(re[0], re[1]); } pii trysend(int x) { assert(x >= 0 && x <= 3); int reallysend = 0; REP(j,4) { bool bit = (lst[x] >> j) & 1; int went = send(bit); reallysend += (went<<j); } return who(reallysend); } pii eat4(){ int raw=0; REP(j,4) { raw += (receive()) << j; } bug(raw); return who(raw); } pii gfrom(pii org, pii t) { pii re; re.f = (t.f>=2?org.s:org.f) * 2 + (t.f&1); re.s = (t.s>=2?org.s:org.f) * 2 + (t.s&1); if (re.f > re.s) swap(re.f, re.s); return re; } void encode(signed N, signed X) { build(); --X; int cur = ((X>>29)&1)*2 + ((X>>28)&1); pii pp = trysend(cur); for (int bit = 27; bit >=0; --bit) { int tosend = 0; if (pp.s == cur) tosend = 2; tosend += (X>>bit)&1; pii go = trysend(tosend); pp = gfrom(pp, go); cur = cur * 2 + ((X>>bit)&1); } } pair<signed, signed> decode(signed N) { build(); pii ee = eat4(); for (int bit = 27; bit >=0; --bit) { pii gt = eat4(); ee = gfrom(ee, gt); } bug(ee.f, ee.s); MN(ee.f, N-1); MN(ee.s, N-1); return {ee.f+1, ee.s+1}; } #ifdef BALBIT signed main(){ ios::sync_with_stdio(0), cin.tie(0); srand(time(0)); // build(); // REP(i,(1<<4)) { // bug(i); // who(i); //// for (int t : who(i)) cout<<t<<' '; //// cout<<endl; // } // for (vector<int> e : st) { // bug(e[0], e[1]); // } // bug(1,2); while (SZ(rar)) rar.pop(); canflip = 1; encode(1000000000, 1000000000); pii p = decode(1000000000); bug(p.f, p.s); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...