#include "message.h"
#include <bits/stdc++.h>
using namespace std;
namespace Encode
{
bool next_bit (vector <bool> &M)
{
if (M.size () == 0) return 0;
bool res = M.back ();
M.pop_back ();
return res;
}
int first_4 (int l, int r, vector <bool> &M, vector <bool> &C)
{
if (l == r) return l;
vector <int> ok_in, ok_out;
for (int i = 0; i <= 30; i ++)
{
if (C[i] == 0)
{
if (l <= i and i <= r and ok_in.size () <= (r - l) / 2)
ok_in.push_back (i);
else ok_out.push_back (i);
}
}
int left_cnt = 0, right_cnt = 0;
for (int i = l; i <= r; i ++)
{
if (C[i] == 0)
{
if (i - l < r - i) left_cnt ++;
if (r - i < i - l) right_cnt ++;
}
}
bool decide = (left_cnt < right_cnt);
vector <bool> next_packet (31, 0);
for (auto i: ok_out) next_packet[i] = next_bit (M);
for (auto i: ok_in) next_packet[i] = decide;
send_packet (next_packet);
int next_group = (r - l) / 2;
if (decide == false) return first_4 (l, l + next_group - 1, M, C);
else return first_4 (r - next_group + 1, r, M, C);
}
void next_29 (int ok, vector <bool> &M, vector <bool> &C)
{
vector <bool> info;
for (int i = 0; i < 31; i ++)
if (i != ok and info.size () < 29)
info.push_back (C[i]);
reverse (info.begin (), info.end ());
for (int i = 0; i < 29; i ++)
{
vector <bool> next_packet (31, 0);
for (int j = 0; j < 31; j ++)
{
if (C[j] == 0)
{
if (j != ok) next_packet[j] = next_bit (M);
else next_packet[j] = next_bit (info);
}
}
send_packet (next_packet);
}
return;
}
void remaining (vector <bool> &M, vector <bool> &C)
{
if (M.size () == 0) return;
vector <bool> next_packet (31, 0);
for (int j = 0; j < 31; j ++)
if (C[j] == 0)
next_packet[j] = next_bit (M);
send_packet (next_packet);
return remaining (M, C);
}
void encode (vector <bool> M, vector <bool> C)
{
M.push_back (1);
reverse (M.begin (), M.end ());
int ok = first_4 (0, 30, M, C);
next_29 (ok, M, C);
remaining (M, C);
}
}
void send_message (vector <bool> M, vector <bool> C)
{
return Encode::encode (M, C);
}
namespace Decode
{
int find_ok (int l, int r, int pos, vector <vector <bool>> &R)
{
if (l == r) return l;
int vote = 0;
for (int i = l; i <= r; i ++)
{
if (R[pos][i]) vote ++;
else vote --;
}
int next_group = (r - l) / 2;
if (vote < 0) return find_ok (l, l + next_group - 1, pos + 1, R);
else return find_ok (r - next_group + 1, r, pos + 1, R);
}
vector <bool> read_C (int ok, vector <vector <bool>> &R)
{
vector <bool> C;
int ok_count = 0;
for (int i = 4; i < 4 + 29; i ++)
{
if (C.size () == ok) C.push_back (0);
C.push_back (R[i][ok]);
if (C.back () == 0) ok_count ++;
}
if (ok_count < 15) C.push_back (0);
else C.push_back (1);
return C;
}
vector <bool> read_first_4 (int l, int r, int pos, vector <vector <bool>> &R, vector <bool> &C)
{
if (l == r) return {};
vector <int> ok_in, ok_out;
for (int i = 0; i < 31; i ++)
{
if (C[i] == 0)
{
if (l <= i and i <= r and ok_in.size () <= (r - l) / 2)
ok_in.push_back (i);
else ok_out.push_back (i);
}
}
vector <bool> ans;
for (auto i: ok_out) ans.push_back (R[pos][i]);
vector <bool> next_ans;
int next_group = (r - l) / 2;
if (R[pos][ok_in[0]] == false) next_ans = read_first_4 (l, l + next_group - 1, pos + 1, R, C);
else next_ans = read_first_4 (r - next_group + 1, r, pos + 1, R, C);
for (auto i: next_ans) ans.push_back (i);
return ans;
}
vector <bool> read_next_29 (int ok, vector <vector <bool>> &R, vector <bool> &C)
{
vector <bool> ans;
for (int i = 4; i < 4 + 29; i ++)
{
for (int j = 0; j < 31; j ++)
{
if (j == ok) continue;
if (C[j] == 0) ans.push_back (R[i][j]);
}
}
return ans;
}
vector <bool> read_remaining (vector <vector <bool>> &R, vector <bool> &C)
{
vector <bool> ans;
for (int i = 4 + 29; i < R.size (); i ++)
for (int j = 0; j < 31; j ++)
if (C[j] == 0)
ans.push_back (R[i][j]);
return ans;
}
vector <bool> decode (vector <vector <bool>> R)
{
int ok = find_ok (0, 30, 0, R);
vector <bool> C = read_C (ok, R);
vector <bool> f4 = read_first_4 (0, 30, 0, R, C);
vector <bool> n29 = read_next_29 (ok, R, C);
vector <bool> remain = read_remaining (R, C);
vector <bool> ans;
for (auto i: f4) ans.push_back (i);
for (auto i: n29) ans.push_back (i);
for (auto i: remain) ans.push_back (i);
while (ans.back () == 0) ans.pop_back ();
ans.pop_back ();
return ans;
}
}
vector <bool> receive_message (vector <vector <bool>> R)
{
return Decode::decode (R);
}
