#include "message.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
ll p[2][31] = {11, 10, 23, 13, 4, 18, 7, 6, 16, 26, 12, 19, 30, 29, 17, 24, 14, 5, 3, 8, 25, 27, 1, 22, 28, 21, 2, 9, 15, 20, 0};
void precomp()
{
for (ll i = 0; i < 31; i++) p[1][30 - i] = p[0][i];
}
ll cost(vector<bool> &c, bool rev)
{
ll tot = 0;
ll ptr = 0, sz = 0;
while (sz < 16)
{
tot++;
for (ll i = 0; i < sz and ptr < 31 and sz < 16; i++, ptr++)
sz += c[p[rev][ptr]] == 0;
if ((16 - sz) * 2 > 31 - ptr)
{
if (c[p[rev][ptr]] == 0)
sz++;
ptr++;
}
}
return tot;
}
void send_message(vector<bool> a, vector<bool> c)
{
precomp();
vector<bool> msg(31, 0);
bool flg = cost(c, 1) < cost(c, 0);
send_packet(vector<bool>(31, flg));
vector<ll> fixed;
ll ptr = 0;
bool ok = false;
while (fixed.size() < 16)
{
ll i;
for (i = 0; i < fixed.size() and ptr < 31; i++, ptr++)
{
msg[fixed[i]] = c[p[flg][ptr]];
if (c[p[flg][ptr]] == 0)
fixed.push_back(p[flg][ptr]);
}
if (i + 3 < fixed.size())
{
for (ll j = 0; j < 4; j++)
msg[fixed[i + j]] = a.size() >> j & 1;
ok = true;
}
if ((16 - fixed.size()) * 2 > 31 - ptr)
{
for (ll i = ptr; i < 31; i++)
msg[i] = c[p[flg][ptr]];
if (c[p[flg][ptr]] == 0)
fixed.push_back(p[flg][ptr]);
ptr++;
}
send_packet(msg);
}
if (fixed.size() != 16)
exit(0);
for (ll i = 0; i < 16; i++)
msg[fixed[i]] = (a.size() >> i & 1);
if (!ok)
send_packet(msg);
for (ll i = 0; i < a.size(); i += 16)
{
for (ll j = 0; j + i < a.size() and j < 16; j++)
msg[fixed[j]] = a[i + j];
send_packet(msg);
}
}
bool majority(vector<bool> &c, ll ind, bool flg)
{
ll cnt1 = 0;
for (ll i = ind; i < 31; i++) cnt1 += c[p[flg][i]];
return cnt1 * 2 > 31 - ind;
}
vector<bool> receive_message(vector<vector<bool>> a)
{
precomp();
vector<bool> c(31, 1);
bool flg = majority(a[0], 0, 0);
ll ptr = 0, cur = 1;
vector<ll> fixed;
bool ok = false;
ll rem = 0;
while (fixed.size() < 16)
{
ll i;
for (i = 0; i < fixed.size() and ptr < 31; i++, ptr++)
{
c[p[flg][ptr]] = a[cur][fixed[i]];
if (c[p[flg][ptr]] == 0)
fixed.push_back(p[flg][ptr]);
}
if (i + 3 < fixed.size())
{
for (ll j = 0; j < 4; j++)
rem += a[cur][fixed[i + j]] ? (1 << j) : 0;
ok = true;
}
if ((16 - fixed.size()) * 2 > 31 - ptr)
{
c[p[flg][ptr]] = majority(a[cur], ptr, flg);
if (c[p[flg][ptr]] == 0)
fixed.push_back(p[flg][ptr]);
ptr++;
}
cur++;
}
if (fixed.size() != 16)
exit(0);
ll sz = 0;
if (!ok)
{
for (ll i = 0; i < 16; i++)
if (a[cur][fixed[i]])
sz += 1 << i;
cur++;
}
else
sz = (a.size() - cur - (rem > 0)) << 4 | rem;
vector<bool> ans(sz);
for (ll i = 0; i < sz; i++)
ans[i] = a[cur + (i >> 4)][fixed[i & 15]];
return ans;
}
