#include "message.h"
#include <bits/stdc++.h>

using namespace std;

bool check(std::vector<bool> C,int p){
    int dig=16;
    int mask=0;
    while(dig){
        if(p&dig){
            mask|=dig;
        }
        int valid_cnt=0;
        int invalid_cnt=0;
        for(int i=0;i<31;i++){
            if((mask&i)!=mask){
                continue;
            }
            if(C[i]){
                invalid_cnt++;
            }else{
                valid_cnt++;
            }
        }
        if(valid_cnt<=invalid_cnt){
            return false;
        }
        dig<<=1;
    }
    return true;
}

std::vector<bool> pack_message(std::vector<bool> m){
    std::vector<bool> res;
    for(bool i:m){
        res.push_back(i);
    }
    res.push_back(true);
    return res;
}


std::vector<bool> unpack_message(std::vector<bool> m){
    std::vector<bool> res;
    int end=-1;
    for(int i=0;i<1025;i++){
        if(m[i]){
            end=i;
        }
    }
    for(int i=0;i<end;i++){
        res.push_back(m[i]);
    }
    return res;
}

bool get_bit(std::vector<bool> m,int& idx){
    if(idx<m.size()){
        return m[idx++];
    }
    idx++;
    return false;
}

void send_message(std::vector<bool> M,std::vector<bool> C){
    int chosen=-1;
    for(int i=0;i<31;i++){
        if(C[i]){
            continue;
        }
        if(!check(C,i)){
            continue;
        }
        chosen=i;
        break;
    }
    std::vector<bool> m=pack_message(M);
    int idx=0;
    {
        int dig=16;
        int mask=0;
        for(int i=0;i<5;i++){
            bool send_bit=chosen&idx;
            int valid_cnt=0;
            int invalid_cnt=0;
            for(int i=0;i<31;i++){
                if((mask&i)!=mask){
                    continue;
                }
                if(C[i]){
                    invalid_cnt++;
                }else{
                    valid_cnt++;
                }
            }
            int borrow_cnt=(valid_cnt-invalid_cnt-1)/2;
            std::vector<bool> p;
            for(int i=0;i<31;i++){
                if(C[i]){
                    p.push_back(false);
                    continue;
                }
                if(borrow_cnt>0){
                    borrow_cnt--;
                    p.push_back(get_bit(m,idx));
                    continue;
                }
                p.push_back(send_bit);
            }
            send_packet(p);
            if(send_bit){
                mask|=dig;
            }
            dig<<=1;
        }
    }
    {
        int j=0;
        for(int i=0;i<30;i++){
            std::vector<bool> p;
            for(int k=0;k<31;k++){
                if(C[k]){
                    p.push_back(false);
                    continue;
                }
                if(k==chosen){
                    p.push_back(C[j]);
                    continue;
                }
                p.push_back(get_bit(m,idx));
            }
            send_packet(p);
            j++;
            if(j==chosen){
                j++;
            }
        }
    }
    while(idx<m.size()){
        std::vector<bool> p;
        for(int k=0;k<31;k++){
            if(C[k]){
                p.push_back(false);
                continue;
            }
            p.push_back(get_bit(m,idx));
        }
        send_packet(p);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    std::vector<bool> res;
    std::vector<bool> C;
    int chosen=-1;
    {
        int dig=16;
        int mask=0;
        for(int k=0;k<5;k++){
            int false_cnt=0;
            int true_cnt=0;
            for(int i=0;i<31;i++){
                if((mask&i)!=mask){
                    continue;
                }
                if(R[k][i]){
                    true_cnt++;
                }else{
                    false_cnt++;
                }
            }
            if(true_cnt>false){
                mask|=dig;
            }
            dig<<=1;
        }
        chosen=mask;
    }
    {
        for(int i=0;i<30;i++){
            if(i==chosen){
                C.push_back(false);
            }
            C.push_back(R[i+5][chosen]);
        }
        if(C.size()<31){
            C.push_back(false);
        }
    }
    {
        int dig=16;
        int mask=0;
        for(int k=0;k<5;k++){
            int valid_cnt=0;
            int invalid_cnt=0;
            for(int i=0;i<31;i++){
                if((mask&i)!=mask){
                    continue;
                }
                if(C[i]){
                    invalid_cnt++;
                }else{
                    valid_cnt++;
                }
            }
            int borrow_cnt=(valid_cnt-invalid_cnt-1)/2;
            for(int i=0;i<31;i++){
                if(C[i]){
                    continue;
                }
                if((mask&i)==mask){
                    if(borrow_cnt>0){
                        borrow_cnt--;
                        res.push_back(R[k][i]);
                    }
                    continue;
                }
                res.push_back(R[k][i]);
            }
            if(chosen&dig){
                mask|=dig;
            }
            dig<<=1;
        }
    }
    for(int k=0;k<30;k++){
        for(int i=0;i<30;i++){
            if(C[i]){
                continue;
            }
            if(i==chosen){
                continue;
            }
            res.push_back(R[k+5][i]);
        }
    }
    for(int k=35,ed=R.size();k<ed;k++){
        for(int i=0;i<30;i++){
            if(C[i]){
                continue;
            }
            res.push_back(R[k][i]);
        }
    }
    return unpack_message(res);
}