Submission #695275

#TimeUsernameProblemLanguageResultExecution timeMemory
695275finn__Flight to the Ford (BOI22_communication)C++17
0 / 100
405 ms200 KiB
#include <bits/stdc++.h> #include "communication.h" using namespace std; // 0 -> 0000, 1 -> 0110, 2 -> 1001, 3 -> 1111 int e[4] = {0, 6, 9, 15}; // The inverse of e including errors. pair<int, int> d[16] = {{0, 2}, // 0000 {0, 2}, // 0001 {0, 1}, // 0010 {1, 2}, // 0011 {0, 1}, // 0100 {0, 3}, // 0101 {1, 3}, // 0110 {1, 3}, // 0111 {0, 2}, // 1000 {0, 2}, // 1001 {0, 3}, // 1010 {2, 3}, // 1011 {1, 2}, // 1100 {2, 3}, // 1101 {1, 3}, // 1110 {1, 3}}; // 1111 int bit_reverse(int N, int X) { int Y = 0; for (int i = 0; i < N; i++) Y |= ((X >> i) & 1) << (N - i - 1); return Y; } void encode(int N, int X) // Sends exactly 120 bits to encode any message. { X = bit_reverse(30, X - 1); // Encode higher-order bits first. for (unsigned i = 0; i < 30; i++) { int Y = e[X & 3], Z = 0; for (unsigned j = 0; j < 4; j++) Z = (Z << 1) | send(Y & 1), Y >>= 1; Z = bit_reverse(4, Z); X >>= 2; X = (X << 1) | (int)(d[Z].second == Y); } } pair<int, int> get_interval(pair<int, int> p, pair<int, int> q, int i) { switch (i) { case 0: return {p.first, (p.first + p.second) / 2}; case 1: return {(p.first + p.second) / 2, p.second}; case 2: return {q.first, (q.first + q.second) / 2}; case 3: return {(q.first + q.second) / 2, q.second}; default: assert(0); } } std::pair<int, int> decode(int N) { pair<int, int> p = {0, 1 << 15}, q = {1 << 15, 1 << 30}; for (unsigned i = 0; i < 30; i++) { int Y = 0; for (unsigned j = 0; j < 4; j++) Y = (Y << 1) | receive(); Y = bit_reverse(4, Y); pair<int, int> r = get_interval(p, q, d[Y].first); q = get_interval(p, q, d[Y].second); p = r; } return {p.first + 1, q.first + 1}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...