#include <bits/stdc++.h>
using namespace std;
/*
The grader provides send_packet() in the sender program.
On the receiver side, only receive_message() is called.
*/
// ================= SENDER SIDE =================
// This will be provided by the grader in the sender program.
// We declare it here so the code compiles.
extern vector<bool> send_packet(vector<bool> A);
// Encode message length S (<= 1024) into 10 bits, MSB first.
static vector<bool> encode_len10(int S) {
vector<bool> bits(10, false);
for (int i = 9; i >= 0; --i) {
bits[9 - i] = ((S >> i) & 1);
}
return bits;
}
void send_message(vector<bool> M, vector<bool> C) {
// Build mask G of reliable indices: 1 = reliable, 0 = controlled
vector<bool> G(31, false);
for (int i = 0; i < 31; ++i) G[i] = !C[i];
// === Phase 1: Send 31 cyclic shifts of G ===
for (int t = 0; t < 31; ++t) {
vector<bool> A(31, false);
for (int i = 0; i < 31; ++i) {
int p = (i + t) % 31;
A[p] = G[i];
}
(void)send_packet(A); // Cleopatra taints, but we ignore here
}
// Reliable indices in ascending order
vector<int> reliable;
for (int i = 0; i < 31; ++i) if (G[i]) reliable.push_back(i);
// Payload: 10-bit header + message bits
vector<bool> payload = encode_len10((int)M.size());
payload.insert(payload.end(), M.begin(), M.end());
// === Phase 2: Send payload, 16 bits per packet ===
size_t pos = 0;
while (pos < payload.size()) {
vector<bool> A(31, false);
for (int j = 0; j < (int)reliable.size(); ++j) {
if (pos < payload.size()) {
A[reliable[j]] = payload[pos++];
}
}
(void)send_packet(A);
}
}
// ================= RECEIVER SIDE =================
// Helper: strict majority from 31 packets
static bool majority31(const array<int,31>& ones, int i) {
return ones[i] > 15; // must be >=16 to win
}
vector<bool> receive_message(vector<vector<bool>> R) {
int P = (int)R.size();
// === Phase 1: reconstruct G ===
array<int,31> ones{}; ones.fill(0);
for (int t = 0; t < 31; ++t) {
for (int i = 0; i < 31; ++i) {
int phys = (i + t) % 31;
if (R[t][phys]) ++ones[i];
}
}
vector<bool> G(31, false);
for (int i = 0; i < 31; ++i) {
G[i] = (ones[i] > 15);
}
// Reliable indices in ascending order
vector<int> reliable;
for (int i = 0; i < 31; ++i) if (G[i]) reliable.push_back(i);
// === Phase 2: parse payload ===
vector<bool> bitstream;
for (int t = 31; t < P; ++t) {
for (int idx : reliable) {
bitstream.push_back(R[t][idx]);
}
}
if (bitstream.size() < 10) return {}; // defensive guard
// First 10 bits = length
int S = 0;
for (int i = 0; i < 10; ++i) {
S = (S << 1) | (bitstream[i] ? 1 : 0);
}
// Next S bits = message
vector<bool> M;
M.reserve(S);
for (int i = 10; i < 10 + S && i < (int)bitstream.size(); ++i) {
M.push_back(bitstream[i]);
}
return M;
}
