#include <bits/stdc++.h>
std::vector<bool> send_packet(std::vector<bool> A);
void send_message(std::vector<bool> M, std::vector<bool> C) {
auto send = [&](const std::string &s) {
std::vector<bool> a(s.length());
for (int i = 0; i < s.length(); ++i) {
a[i] = s[i] == '1';
}
send_packet(a);
};
// to get the good average case
std::mt19937 gen(69420);
std::vector<int> p(31);
std::iota(p.begin(), p.end(), 0);
std::shuffle(p.begin(), p.end(), gen);
auto send_num_unlocked = [&](int n, int bits) { // assumes receiver only knows first `bits` bits
std::string msg(31, '0');
for (int i = 0, j = 0; i < bits; ++i, ++j) {
while (C[p[j]]) {
j++;
}
msg[p[j]] = !!(n & 1 << i) + '0';
}
send(msg);
};
auto send_num = [&](int n) {
send_num_unlocked(n, 16);
};
int bits = 0;
for (int i = 0; i < 31; ++i) {
if (bits < 2) {
send(std::string(31, C[p[i]] + '0'));
bits += !C[p[i]];
} else {
int x = 0;
int n_bits = bits;
for (int j = 0; j < bits and i + j < 31; ++j) {
x += int(C[p[i + j]]) << j;
n_bits += !C[p[i + j]];
}
i += bits - 1;
send_num_unlocked(x, bits);
bits = n_bits;
}
}
send_num(M.size());
for (int i = 0; i < M.size(); i += 16) {
int x = 0;
for (int j = 0; j < 16 and i + j < M.size(); ++j) {
x += int(M[i + j]) << j;
}
send_num(x);
}
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
auto recv = [&](std::vector<bool> P) {
int o = 0, z = 0;
for (bool i : P) {
o += i, z += !i;
}
return o > z;
};
std::vector<bool> C(31, true);
std::mt19937 gen(69420);
std::vector<int> p(31);
std::iota(p.begin(), p.end(), 0);
std::shuffle(p.begin(), p.end(), gen);
auto recv_num_unlocked = [&](std::vector<bool> P, int bits) {
int ans = 0;
for (int i = 0, j = 0; i < bits; ++i, ++j) {
while (C[p[j]]) {
j++;
}
ans += int(P[p[j]]) << i;
}
return ans;
};
int cur = 0;
int bits = 0;
for (int i = 0; i < 31; ++i) {
if (bits < 2) {
C[p[i]] = recv(R[cur++]);
bits += !C[p[i]];
} else {
int x = recv_num_unlocked(R[cur++], bits);
int n_bits = bits;
for (int j = 0; j < bits and i + j < 31; ++j) {
C[p[i + j]] = x & 1 << j;
n_bits += !C[p[i + j]];
}
i += bits - 1;
bits = n_bits;
}
}
assert(bits == 16);
auto recv_num = [&](std::vector<bool> P) {
return recv_num_unlocked(P, 16);
};
int size = recv_num(R[cur++]);
std::vector<bool> M(size);
for (int i = 0; i < size; i += 16) {
int x = recv_num(R[cur++]);
for (int j = 0; j < 16 and i + j < size; ++j) {
M[i + j] = x & 1 << j;
}
}
return M;
}
