#include <array>
#include <iostream>
using i64 = int64_t;
int send(int s);
int receive();
constexpr const i64 FIB[32] = {
1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,
121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};
// 252, 149, 8, 104, 154
// ['11111100', '10010101', '00001000', '01101000', '10011010']
constexpr const int STRINGS[5][8] = {
{1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 0},
};
constexpr const std::pair<int, int> STRINGS_BACKWARDS[256] = {
{1, 2}, {1, 2}, {2, 0}, {0, 1}, {1, 0}, {1, 0}, {0, 1}, {1, 0}, {2, 4},
{2, 0}, {2, 4}, {4, 0}, {2, 0}, {2, 0}, {4, 0}, {4, 0}, {1, 4}, {1, 0},
{4, 0}, {4, 0}, {1, 0}, {1, 0}, {0, 1}, {1, 0}, {2, 4}, {2, 0}, {2, 4},
{4, 0}, {1, 2}, {1, 2}, {4, 0}, {1, 4}, {2, 3}, {2, 3}, {2, 3}, {0, 1},
{0, 1}, {0, 1}, {0, 1}, {0, 1}, {2, 3}, {2, 3}, {2, 3}, {0, 1}, {2, 3},
{2, 3}, {0, 1}, {0, 1}, {1, 4}, {1, 0}, {4, 0}, {4, 0}, {1, 0}, {1, 0},
{0, 1}, {1, 0}, {3, 4}, {3, 0}, {3, 4}, {4, 0}, {1, 3}, {1, 3}, {4, 0},
{1, 4}, {2, 3}, {2, 3}, {2, 3}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1},
{2, 3}, {2, 3}, {2, 3}, {0, 1}, {2, 3}, {2, 3}, {0, 1}, {0, 1}, {0, 1},
{0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 2}, {0, 2},
{2, 0}, {0, 1}, {0, 2}, {0, 2}, {0, 1}, {0, 1}, {3, 0}, {3, 0}, {3, 0},
{0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3}, {3, 0}, {0, 1},
{0, 3}, {0, 3}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1},
{0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3}, {3, 0}, {0, 1}, {0, 3}, {0, 3},
{0, 1}, {0, 1}, {1, 2}, {1, 2}, {2, 0}, {0, 1}, {1, 0}, {1, 0}, {0, 1},
{1, 0}, {2, 4}, {2, 0}, {2, 4}, {4, 0}, {2, 0}, {2, 0}, {4, 0}, {4, 0},
{1, 4}, {1, 0}, {4, 0}, {4, 0}, {1, 0}, {1, 0}, {0, 1}, {1, 0}, {2, 4},
{2, 0}, {2, 4}, {4, 0}, {1, 2}, {1, 2}, {4, 0}, {1, 4}, {2, 0}, {2, 0},
{2, 0}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 2}, {0, 2}, {2, 0},
{0, 1}, {0, 2}, {0, 2}, {0, 1}, {0, 1}, {1, 4}, {1, 0}, {4, 0}, {4, 0},
{0, 1}, {0, 1}, {0, 1}, {1, 0}, {0, 4}, {0, 1}, {4, 0}, {4, 0}, {0, 1},
{0, 1}, {0, 4}, {1, 4}, {1, 3}, {1, 3}, {3, 0}, {0, 1}, {1, 0}, {1, 0},
{0, 1}, {1, 0}, {3, 4}, {3, 0}, {3, 4}, {4, 0}, {3, 0}, {3, 0}, {4, 0},
{4, 0}, {1, 4}, {1, 0}, {4, 0}, {4, 0}, {0, 1}, {0, 1}, {0, 1}, {1, 0},
{0, 4}, {0, 1}, {4, 0}, {4, 0}, {0, 1}, {0, 1}, {0, 4}, {1, 4}, {3, 0},
{3, 0}, {3, 0}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3},
{3, 0}, {0, 1}, {0, 3}, {0, 3}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1},
{0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 1}, {0, 3}, {0, 3}, {3, 0}, {0, 1},
{0, 3}, {0, 3}, {0, 1}, {0, 1}};
void encode(int n, int x) {
x -= 1;
if (n <= 5) {
for (i64 i = 0; i < 8; i++) {
send(STRINGS[x][i]);
}
} else {
i64 error = 0;
for (i64 i = 0; 1 << i < n; i++) {
int value = x & (1 << i) ? 1 : 0;
std::cerr << value << '\n';
if (send(value) != value) {
error += FIB[i];
}
}
i64 bits = 0;
while (1 << bits < n) bits += 1;
encode(FIB[bits], error + 1);
}
}
int decompress(int n) {
int result = 0;
for (i64 i = 31; i >= 0; i--) {
if (n >= FIB[i]) {
n -= FIB[i];
result |= 1 << i;
}
}
return result;
}
std::pair<int, int> decode(int n) {
if (n <= 5) {
i64 read = 0;
for (i64 i = 0; i < 8; i++) {
read |= receive() << (7 - i);
}
auto [x, y] = STRINGS_BACKWARDS[read];
std::cerr << x << ' ' << y << '\n';
return {x + 1, std::min(y + 1, n)};
} else {
int message = 0;
for (i64 i = 0; 1 << i < n; i++) {
message |= receive() << i;
}
i64 bits = 0;
while (1 << bits < n) bits += 1;
auto [corr1, corr2] = decode(FIB[bits]);
auto [x, y] = std::array<int, 2>{message ^ decompress(corr1 - 1),
message ^ decompress(corr2 - 1)};
return {std::min(x + 1, n), std::min(y + 1, n)};
}
}
