#include "message.h"
#include <bits/stdc++.h>
using namespace std;
static const int W = 31;
static const int SAFE = 16;
static const int QP = 66;
static const int LEN = 1025;
void send_message(vector<bool> M, vector<bool> C) {
vector<int> safe;
for (int i = 0; i < W; i++) if (!C[i]) safe.push_back(i);
vector<int> x(W, 100);
for (int k = 0; k < SAFE; k++) {
int a = safe[k];
int b = safe[(k + 1) % SAFE];
int d = (b - a + W) % W;
if (d == 0) d = W;
x[a] = d;
}
int S = (int)M.size();
vector<bool> msg;
msg.reserve(LEN);
int pref = 1024 - S;
for (int i = 0; i < pref; i++) msg.push_back(false);
msg.push_back(true);
for (bool b : M) msg.push_back(b);
int ptr = 0;
for (int t = 1; t <= QP; t++) {
vector<bool> p(W, false);
for (int i = 0; i < W; i++) {
if (C[i]) {
p[i] = false;
} else {
if (t < x[i]) p[i] = false;
else if (t == x[i]) p[i] = true;
else p[i] = msg[ptr++];
}
}
send_packet(p);
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
int Q = (int)R.size();
vector<int> first1(W, Q + 1);
for (int i = 0; i < W; i++) {
for (int t = 1; t <= Q; t++) {
if (R[t - 1][i]) { first1[i] = t; break; }
}
}
vector<int> to(W);
for (int i = 0; i < W; i++) {
int d = first1[i];
if (d > W) d = W;
to[i] = (i + d) % W;
}
vector<int> vis(W, 0), inst(W, 0), parent(W, -1);
vector<int> cycle_nodes;
for (int i = 0; i < W; i++) if (!vis[i]) {
int v = i;
while (!vis[v]) {
vis[v] = 1;
inst[v] = 1;
v = to[v];
}
int u = i;
while (inst[u]) {
inst[u] = 0;
u = to[u];
}
}
vector<int> mark(W, 0), state(W, 0);
vector<int> stackv;
function<void(int)> dfs = [&](int s){
int v = s;
while (state[v] == 0) {
state[v] = 1;
stackv.push_back(v);
v = to[v];
}
if (state[v] == 1) {
vector<int> cyc;
for (int j = (int)stackv.size() - 1; j >= 0; j--) {
cyc.push_back(stackv[j]);
if (stackv[j] == v) break;
}
reverse(cyc.begin(), cyc.end());
if ((int)cyc.size() == SAFE) cycle_nodes = cyc;
}
while (!stackv.empty()) {
int u = stackv.back();
stackv.pop_back();
state[u] = 2;
if (u == v) break;
}
};
for (int i = 0; i < W; i++) if (state[i] == 0) dfs(i);
vector<int> safe = cycle_nodes;
sort(safe.begin(), safe.end());
vector<int> x(W, 0);
for (int i = 0; i < W; i++) x[i] = first1[i];
vector<bool> bits;
bits.reserve(LEN);
for (int t = 1; t <= QP; t++) {
for (int pos : safe) {
if (t > x[pos]) bits.push_back(R[t - 1][pos]);
}
}
int k = 0;
while (k < (int)bits.size() && !bits[k]) k++;
k++;
vector<bool> M;
if (k <= (int)bits.size()) {
M.assign(bits.begin() + k, bits.end());
}
return M;
}
