#include <bits/stdc++.h>
#include "message.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 1000 * 1000 + 7;
int sum[40];
vector<bool> M;
int il = 0, cnt = 0;
inline int S(int a, int b)
{
return sum[b + 1] - sum[a];
}
bool Nxt()
{
if(cnt >= (int)M.size()) return 0;
return M[cnt++];
}
void send_message(vector<bool> _M, vector<bool> C)
{
il = 0; cnt = 0;
for(int i = 0; i < 36; ++i) sum[i] = 0;
_M.pb(1);
M = _M;
vector<int> pos;
vector<bool> bas(31, false);
vector<vector<bool>> answer(100, bas);
for(int i = 0; i < (int)C.size(); ++i)
{
sum[i + 1] = sum[i] + (int)(1 ^ C[i]);
if(C[i] == 0)
pos.pb(i);
}
int p = 0, k = 30;
while(p + 1 < k)
{
//cerr << "BS1: " << p << " " << k << "\n";
bool r = !(S(p, (p + k) / 2 - 1) >= (k - p + 2) / 4);
if(p + 2 == k && C[p] == 0) r = 0;
if(p + 2 == k && C[p] != 0) r = 1;
for(int i = 0; i < (int)pos.size(); ++i)
{
if(pos[i] < p || pos[i] > k) answer[il][pos[i]] = Nxt();
else answer[il][pos[i]] = r;
}
if(r)
p = (p + k) / 2 + 1;
else
k = (p + k) / 2 - 1;
++il;
}
//cerr << "fp " << p << "\n";
for(int i = 0; i < 30; ++i)
if(i < p)
answer[il + i][p] = C[i];
else
answer[il + i][p] = C[i + 1];
for(int i = 0; i < 30; ++i)
for(int j = 0; j < (int)pos.size(); ++j)
if(pos[j] != p)
answer[il + i][pos[j]] = Nxt();
il += 29;
while(cnt < (int)M.size())
{
++il;
for(int j = 0; j < (int)pos.size(); ++j)
answer[il][pos[j]] = Nxt();
}
for(int i = 0; i <= il; ++i)
send_packet(answer[i]);
//cerr << "xd\n";
}
vector<bool> receive_message(vector<vector<bool>> R)
{
il = 0; cnt = 0;
int p = 0, k = 30;
vector<int> pos;
vector<pair<int, int>> ran;
vector<bool> ans;
while(p + 1 < k)
{
//cerr << "BS2: " << p << " " << k << "\n";
ran.pb(make_pair(p, k));
int bal = 0;
for(int i = p; i <= k; ++i)
bal += (int)R[il][i];
if(bal < (k - p + 2) / 2)
k = (p + k) / 2 - 1;
else
p = (p + k) / 2 + 1;
++il;
}
//cerr << "fp2 " << p << "\n";
for(int i = 0; i < 30; ++i)
{
if(i == p) pos.pb(p);
int dod = 0;
if(i >= p) ++dod;
if(R[il + i][p] == 0)
pos.pb(i + dod);
}
if((int)pos.size() < 16) pos.pb(30);
//cerr << "xd2\n";
//cerr << R.size() << " Pos: \n";
//for(int i = 0; i < (int)pos.size(); ++i)
//cerr << pos[i] << " ";
//cerr << "\n";
for(int i = 0; i < il; ++i)
for(int j = 0; j < (int)pos.size(); ++j)
if(pos[j] < ran[i].st || pos[j] > ran[i].nd)
ans.pb(R[i][pos[j]]);
for(int i = 0; i < 30; ++i)
{
for(int j = 0; j < (int)pos.size(); ++j)
if(pos[j] != p)
ans.pb(R[il + i][pos[j]]);
}
il += 30;
for(il = il; il < (int)R.size(); ++il)
for(int j = 0; j < (int)pos.size(); ++j)
ans.pb(R[il][pos[j]]);
while(ans.back() == 0) ans.pop_back();
ans.pop_back();
return ans;
}
