#include "message.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int B[40][40];
int mxval[5];
int val[5];
int lv[40];
int isval[40];
void init() {
int i, j;
for (i = 0; i <= 32; i++) {
for (j = 0; j <= i; j++) {
if (i == j || i == 0 || j == 0) B[i][j] = 1;
else B[i][j] = B[i - 1][j] + B[i - 1][j - 1];
}
}
}
void init_A() {
int i;
init();
memset(mxval, 0, sizeof(mxval));
memset(lv, 0, sizeof(lv));
for (i = 0; i < 4; i++) mxval[i] = B[1 << (4 - i)][1 << (3 - i)];
}
void init_B() {
int i;
init();
memset(lv, 0, sizeof(isval));
}
void send_message(std::vector<bool> M, std::vector<bool> C) {
init_A();
M.push_back(1);
M.resize(1025);
int i;
int lastbit = 0;
for (i = 0; i < 23; i++) if (M[M.size() - 23 + i]) lastbit |= (1 << i);
M.resize(M.size() - 23);
for (i = 3; i >= 0; i--) {
val[i] = lastbit % mxval[i];
lastbit /= mxval[i];
}
assert(lastbit == 0);
int ptr = 0;
auto getnext = [&]() {
if (ptr >= M.size()) return false;
return (bool)M[ptr++];
};
int d;
//for (i = 0; i < 31; i++) if (!C[i]) lv[i] = 0;
for (d = 0; d < 4; d++) {
vector<bool> v;
int N = 1 << (3 - d); //len: 2N, choose N indexes
for (i = 0; i < N; i++) v.push_back(0);
for (i = 0; i < N; i++) v.push_back(1);
for (i = 0; i < val[d]; i++) next_permutation(v.begin(), v.end());
int p = 0;
vector<bool> sv(31);
for (i = 0; i < 31; i++) if (!C[i]) {
if (lv[i] == d) sv[i] = v[p++];
else sv[i] = getnext();
}
auto res = send_packet(sv);
int cnt[2] = { 0, 0 };
for (i = 0; i < 31; i++) if (lv[i] == d && C[i]) cnt[res[i]]++;
int c = 0;
if (cnt[0] > cnt[1]) c = 1;
for (i = 0; i < 31; i++) if (lv[i] == d && res[i] == c) lv[i]++;
}
int key = 0;
for (i = 0; i < 31; i++) {
if (lv[i] == 4) {
key = i;
break;
}
}
for (d = 0; d < 4; d++) val[d] = 0;
for (d = 0; d < 4; d++) {
int t, f;
t = f = 0;
vector<int> v;
for (i = 0; i < 31; i++) if (lv[i] == d) {
v.push_back(C[i]);
if (C[i]) f++;
else t++;
}
mxval[d] = B[t + f][t];
while (prev_permutation(v.begin(), v.end())) val[d]++;
}
int sum = 0;
for (i = 0; i < 4; i++) {
sum *= mxval[i];
sum += val[i];
}
int rem = 24;
while (ptr < M.size()) {
vector<bool> sv(31);
for (i = 0; i < 31; i++) {
if (C[i]) continue;
if (i == key && rem) {
rem--;
sv[i] = sum & 1;
sum >>= 1;
}
else sv[i] = getnext();
}
send_packet(sv);
}
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
init_B();
int d, i;
for (d = 0; d < 4; d++) {
int cnt[2] = { 0, 0 };
for (i = 0; i < 31; i++) if (lv[i] == d) cnt[R[d][i]]++;
int c = 0;
if (cnt[0] > cnt[1]) c = 1;
for (i = 0; i < 31; i++) if (lv[i] == d && R[d][i] == c) lv[i]++;
}
int key = 0;
int lcnt[4] = { 0, 0, 0, 0 };
for (i = 0; i < 31; i++) {
if (lv[i] == 4) key = i;
else lcnt[lv[i]]++;
}
for (i = 0; i < 4; i++) mxval[i] = B[lcnt[i]][1 << (3 - i)];
int mul = 0;
for (i = 0; i < 24; i++) if (R[i + 4][key]) mul |= (1 << i);
for (i = 3; i >= 0; i--) {
val[i] = mul % mxval[i];
mul /= mxval[i];
}
isval[key] = 1;
for (d = 0; d < 4; d++) {
vector<int> v(lcnt[d], 1);
for (i = 0; i < (1 << 3 - d); i++) v[i] = 0;
for (i = 0; i < val[d]; i++) next_permutation(v.begin(), v.end());
int p = 0;
for (i = 0; i < 31; i++) if (lv[i] == d) isval[i] = 1 - v[p++];
}
vector<bool> ans;
for (d = 1; d < 4; d++) {
for (i = 0; i < 31; i++) {
if (isval[i] && lv[i] < d) {
ans.push_back(R[d][i]);
}
}
}
for (d = 4; d < R.size(); d++) {
for (i = 0; i < 31; i++) if (isval[i]) {
if (i == key && d < 28) continue;
ans.push_back(R[d][i]);
}
}
assert(ans.size() >= 1002);
ans.resize(1002);
for (i = 0; i < 4; i++) mxval[i] = B[1 << (4 - i)][1 << (3 - i)];
for (d = 0; d < 4; d++) {
vector<int> v;
for (i = 0; i < 31; i++) if (isval[i] && lv[i] >= d) v.push_back(R[d][i]);
val[d] = 0;
while (prev_permutation(v.begin(), v.end())) val[d]++;
}
int lastbit = 0;
for (i = 0; i < 4; i++) {
lastbit *= mxval[i];
lastbit += val[i];
}
for (i = 0; i < 23; i++) {
ans.push_back(lastbit & 1);
lastbit >>= 1;
}
while (!ans.back()) ans.pop_back();
ans.pop_back();
return ans;
}
