#include "message.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
// send_packet(A);
int perm[31] = {28,23,16,0,2,10,7,18,11,14,9,27,19,17,15,4,12,24,3,21,6,30,1,25,5,26,29,8,20,22,13};
void send_message(vector<bool> M, vector<bool> C) {
int mlen = sz(M);
for(int i = 10;i>=0;i--){
M.insert(M.begin() , mlen & (1 << i));
}
vector<bool> A(31, 1);// use this vector
vector<int>released;// indexes in this vector will start sending the message
// 1 : find a safe bit
int msgsayac = 0;
int PACKET = 0;
function<int(int,int)> search = [&](int l , int r){
if(l == r)return l;
int mid = (l + r) / 2;// <= mid , > mid
int cnt = 0;
for(int i = l;i<=mid;i++)cnt += C[perm[i]] == 0;
if(2 * cnt > (mid - l + 1)){
for(int i = l;i<=r;i++)A[perm[i]] = 0;
for(auto itr : released){
if(msgsayac == sz(M))break;
A[perm[itr]] = M[msgsayac++];
}
PACKET++;
send_packet(A);
for(int i = mid+1;i<=r;i++)if(C[perm[i]] == 0)released.push_back(i);
sort(all(released));
return search(l , mid);
}
else{
for(int i = l;i<=r;i++)A[perm[i]] = 1;
for(auto itr : released){
if(msgsayac == sz(M))break;
A[perm[itr]] = M[msgsayac++];
}
PACKET++;
send_packet(A);
for(int i = l;i<=mid;i++)if(C[perm[i]] == 0)released.push_back(i);
sort(all(released));
return search(mid+1 , r);
}
};
int safebit = search(0,30);
// cerr << "1 safe bit : " << safebit << endl;
// 2 : show all
for(int i = 0;i<31;i++){
if(i == safebit)continue;
A[perm[safebit]] = C[perm[i]];
// cerr << PACKET << " sent : " << i << " = " << C[i] << endl;
for(auto itr : released){
if(msgsayac == sz(M))break;
A[perm[itr]] = M[msgsayac++];
}
PACKET++;
send_packet(A);
}
released.push_back(safebit);
sort(all(released));
// 3 : finish the message
while(msgsayac < sz(M)){
for(auto itr : released){
if(msgsayac == sz(M))break;
A[perm[itr]] = M[msgsayac++];
}
send_packet(A);
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
int mlen = 0 , lensayac = 0;
vector<bool>M;
int state = 0;
int l = 0 , r = 30 , safebit = -1 , cur = 0 , crit[31] , indx = 0;
memset(crit , -1 , sizeof(crit));
vector<int>vsafe;
int PACKET = 0;
for(auto packet : R){
if(state == 0){
int mid = (l + r) / 2;
int cnt = 0;
for(int i = l;i<=r;i++){
cnt += packet[perm[i]] == 0;
}
if(2 * cnt > (r - l + 1)){// sola
for(int i = mid+1;i<=r;i++)crit[perm[i]] = indx+1;
r = mid;
}
else{
for(int i = l;i<=mid;i++)crit[perm[i]] = indx+1;
l = mid+1;
}
if(l == r){
safebit = l;
vsafe.push_back(safebit);
state = 1;
}
}
else if(state == 1){
if(cur == safebit)cur++;
if(packet[perm[safebit]] == 0){
// cout << "BRUH : " << PACKET << " " << cur << endl;
vsafe.push_back(cur);
}
cur++;
if(cur == safebit)cur++;
if(cur == 31){
state = 2;
crit[perm[safebit]] = indx+1;
}
}
indx++;
PACKET++;
}
// cerr << "2 safe bit : " << safebit << endl;
sort(all(vsafe));
// cerr << "vsafe : ";for(auto itr : vsafe)cout << itr << " ";cout << endl;
for(int i = 0;i<sz(R);i++){
for(auto itr : vsafe){
if(i < crit[perm[itr]])continue;
if(lensayac <= 10){
mlen += R[i][perm[itr]] * (1 << lensayac);
lensayac++;
}
else{
M.push_back(R[i][perm[itr]]);
}
}
}
// cout << "mlen : " << mlen << endl;
while(sz(M) > mlen)M.pop_back();
return M;
}
