#include "message.h"

std::vector<bool> P(31);
std::vector<int> A;

void solve_alice(int l, int r, std::vector<bool> &C) {
    if (l == r) {
        return A.push_back(l);
    }

    int mid = (l + r) >> 1, cntL = 0, cntR = 0, i;
    for (i = l; i <= mid; i ++) {
        cntL += !C[i];
    }
    for (i = mid + 1; i <= r; i ++) {
        cntR += !C[i];
    }

    if (cntL > cntR) {
        send_packet(std::vector<bool>(31, false));
        solve_alice(l, mid, C);

        for (i = mid + 1; i <= r && i - mid <= A.size(); i ++) {
            if (!(P[A[i - mid - 1]] = C[i])) {
                A.push_back(i);
            }
        }
        send_packet(P);

        while (i <= r) {
            A.push_back(i ++);
        }
    } else {
        send_packet(std::vector<bool>(31, true));
        solve_alice(mid + 1, r, C);

        for (i = l; i <= mid && i - l < A.size(); i ++) {
            if (!(P[A[i - l]] = C[i])) {
                A.push_back(i);
            }
        }
        send_packet(P);

        while (i <= mid) {
            A.push_back(i ++);
        }
    }
}

void solve_bob(int l, int r, std::vector<std::vector<bool>> &R, int &cur) {
    if (l == r) {
        return A.push_back(l);
    }

    int mid = (l + r) >> 1, cnt = 0, i;
    for (bool x : R[cur]) {
        cnt += x;
    }
    cur ++;

    if (cnt << 1 < 31) {
        solve_bob(l, mid, R, cur);
        for (i = mid + 1; i <= r && i - mid <= A.size(); i ++) {
            if (!R[cur][A[i - mid - 1]]) {
                A.push_back(i);
            }
        }
        while (i <= r) {
            A.push_back(i ++);
        }
    } else {
        solve_bob(mid + 1, r, R, cur);
        for (i = l; i <= mid && i - l < A.size(); i ++) {
            if (!R[cur][A[i - l]]) {
                A.push_back(i);
            }
        }
        while (i <= mid) {
            A.push_back(i ++);
        }
    }

    cur ++;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
    A.clear();
    solve_alice(0, 30, C);

    for (int i = 0; i < 4; i ++) {
        P[A[i]] = M.size() >> i & 1;
    }
    send_packet(P);

    for (int i = 0; i < M.size(); i += 16) {
        for (int j = i; j < i + 16 && j < M.size(); j ++) {
            P[A[j - i]] = M[j];
        }
        send_packet(P);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    std::vector<bool> M;
    int cur = 0;

    A.clear();
    solve_bob(0, 30, R, cur);
    // ...

    int res = 0;
    for (int i = 0; i < 4; i ++) {
        res |= R[cur][A[i]] << i;
    }
    if (!res) {
        res = 16;
    }

    for (int i = cur + 1; i + 1 < R.size(); i ++) {
        for (int j = 0; j < 16; j ++) {
            M.push_back(R[i][A[j]]);
        }
    }
    for (int i = 0; i < res; i ++) {
        M.push_back(R.back()[A[i]]);
    }

    return M;
}