#include "message.h"
#include <bits/stdc++.h>
#define ar array
using namespace std;
vector<bool> c;
int freq(int l, int r){
int sum = 0;
for(int i=l; i<=r; i++){
sum += !c[i];
}
return sum;
}
void send_message(std::vector<bool> M, std::vector<bool> C) {
int s = M.size();
int idm = 0;
c = C;
vector<bool> ini[4];
for(int i=0; i<4; i++){
ini[i].resize(31);
}
int l=0, r=30;
for(int i=0; l+1<r; i++){
int m = (r+l) >> 1;
if(freq(l, m) >= (m-l+1)/2 + 1){
for(int j=0; j<=30; j++){
if(j >= l and j <= r) ini[i][j] = 0;
else if(!c[j] and idm < s){
ini[i][j] = M[idm++];
}
}
r = m;
}
else{
for(int j=0; j<=30; j++){
if(j >= l and j <= r) ini[i][j] = 1;
else if(!c[j] and idm < s){
ini[i][j] = M[idm++];
}
}
l = m+1;
}
// cout << i << endl;
// for(int x : ini[i]) cout << x << " ";
// cout << endl;
send_packet(ini[i]);
}
// cout << "LR " << l << " " << r << endl;
bool first = 0;
for(int i=0; i<=30; i++){
if(i == l or i == r) continue;
vector<bool> cur(31, 0);
cur[l] = c[i];
cur[r] = c[i+1];
// cout << i << " " << i+1 << " " << cur[l] << " " << cur[r] << endl;
i++;
if(!first){
// query with id == 4
first = 1;
for(int j=0, k=0; j<=30; j++){
if(!c[j] and j != l and j != r){
cur[j] = (s & (1<<k));
k++;
}
}
}
else{
for(int j=0; j<=30; j++){
if(j >= l and j <= r) continue;
if(!c[j] and idm < s){
cur[j] = M[idm++];
}
}
}
send_packet(cur);
}
while(idm < s){
vector<bool> cur(31, 0);
for(int j=0; j<=30; j++){
if(!c[j] and idm < s){
cur[j] = M[idm++];
}
}
send_packet(cur);
}
}
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
int l = 0, r = 30, sum, id = 0;
vector<ar<int,2>> ranges;
while(id<4){
int m = (l + r) >> 1;
sum = 0;
for(int i=l; i<=r; i++) sum += R[id][i];
ranges.push_back({l, r});
int majority = (r-l+1)/2 + 1;
if(sum < majority){
r = m;
}
else{
l = m+1;
}
// for(int i=0; i<=30; i++) cout << R[id][i] << " ";
// cout << endl;
id++;
}
vector<bool> ans(31, 0);
// cout << l << " " << r << endl;
for(int i=0; i<=30; i++){
if(i == l or i == r) continue;
ans[i] = R[id][l];
ans[i+1] = R[id][r];
// cout << i << " " << i+1 << " " << R[id][l] << " " << R[id][r] << endl;
ranges.push_back({l, r});
i++;
id++;
}
while(ranges.size() < R.size()) ranges.push_back({-1, -1});
// for(bool x : ans) cout << x << " ";
// cout << endl;
int s = 0;
for(int i=0, k=0; i<=30; i++){
if(!ans[i] and i != l and i != r){
s |= (R[4][i]<<k);
k++;
}
}
// cout << s << endl;
vector<bool> message;
int i = 0;
while((int)message.size() < s){
for(int j=0; j<=30; j++){
if((int)message.size() == s or ans[j] or (j >= ranges[i][0] and j <= ranges[i][1])) continue;
// cout << i << " " << message.size()+1 << endl;
message.push_back(R[i][j]);
}
i++;
if(i == 4) i++;
}
return message;
}
