#include "message.h"
#include <bits/stdc++.h>
using namespace std;
static const int N = 31;
static const int GOOD = 16;
static const int PACKETS = 66;
static const int PAYLOAD = 1025;
// ------------------------------------------------------------
// Helpers
// ------------------------------------------------------------
static vector<int> get_good_positions_from_C(const vector<bool>& C) {
vector<int> a;
for (int i = 0; i < N; ++i) {
if (!C[i]) a.push_back(i);
}
return a; // size = 16, already sorted increasingly
}
static vector<int> get_diffs(const vector<int>& a) {
vector<int> d(GOOD);
for (int i = 0; i < GOOD; ++i) {
d[i] = (a[(i + 1) % GOOD] - a[i] + N) % N;
if (d[i] == 0) d[i] = N; // should never happen here
}
return d;
}
// T = 0...(1024-S times)...01M, total length = 1025
static vector<bool> build_payload(const vector<bool>& M) {
vector<bool> T;
T.reserve(PAYLOAD);
int S = (int)M.size();
int zeros = 1024 - S;
for (int i = 0; i < zeros; ++i) T.push_back(false);
T.push_back(true);
for (bool b : M) T.push_back(b);
return T;
}
// ------------------------------------------------------------
// Sender
// ------------------------------------------------------------
void send_message(std::vector<bool> M, std::vector<bool> C) {
vector<int> a = get_good_positions_from_C(C);
vector<int> d = get_diffs(a);
vector<bool> T = build_payload(M);
vector<vector<bool>> A(PACKETS, vector<bool>(N, false));
int ptr = 0;
// For each good column a[i]:
// - first d[i] slots: one-hot encoding of d[i] => 00...001
// - remaining slots: payload bits
for (int i = 0; i < GOOD; ++i) {
int col = a[i];
// one-hot code of value d[i]
for (int r = 0; r < d[i] - 1; ++r) A[r][col] = false;
A[d[i] - 1][col] = true;
// remaining slots carry payload
for (int r = d[i]; r < PACKETS; ++r) {
A[r][col] = T[ptr++];
}
}
// Exactly 31 overhead bits, so 66*16 - 31 = 1025 payload bits.
// Hence ptr must be exactly PAYLOAD.
for (int r = 0; r < PACKETS; ++r) {
send_packet(A[r]);
}
}
// ------------------------------------------------------------
// Receiver
// ------------------------------------------------------------
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
vector<int> nxt(N, 0);
// For each position i, let first1(i) be the first packet (1..16)
// where R[packet][i] == 1. For good positions this equals d_i.
// Then define edge i -> (i + first1(i)) mod 31.
// If there is no 1 in first 16 packets, the vertex cannot be good;
// any arbitrary self-loop is fine.
for (int i = 0; i < N; ++i) {
int first = -1;
for (int r = 0; r < GOOD; ++r) {
if (R[r][i]) {
first = r + 1; // 1-based
break;
}
}
if (first == -1) nxt[i] = i; // arbitrary
else nxt[i] = (i + first) % N;
}
// Find the unique directed cycle of length 16.
vector<int> cycle;
for (int start = 0; start < N; ++start) {
vector<int> seen_order(N, -1);
vector<int> path;
int cur = start;
bool ok = true;
for (int step = 0; step < GOOD; ++step) {
if (seen_order[cur] != -1) {
ok = false;
break;
}
seen_order[cur] = step;
path.push_back(cur);
cur = nxt[cur];
}
if (ok && cur == start) {
cycle = path;
break;
}
}
sort(cycle.begin(), cycle.end()); // this is a1 < a2 < ... < a16
vector<int> d = get_diffs(cycle);
// Extract payload from the unused cells in the good columns.
vector<bool> T;
T.reserve(PAYLOAD);
for (int i = 0; i < GOOD; ++i) {
int col = cycle[i];
for (int r = d[i]; r < PACKETS; ++r) {
T.push_back(R[r][col]);
}
}
// T has the form 0...01M. Return suffix after the first 1.
int pos = 0;
while (pos < (int)T.size() && !T[pos]) ++pos;
vector<bool> M;
for (int i = pos + 1; i < (int)T.size(); ++i) {
M.push_back(T[i]);
}
return M;
}
