#include "message.h"
#include <bits/stdc++.h>
using namespace std;
void send_message(vector<bool> M, vector<bool> C) {
int S = M.size();
int msg_ptr = 0;
// We assume standard packet size of 31.
// We limit our search to the first 16 bits [0..15].
// Due to Pigeonhole Principle (31 total, 16 safe, 15 Cleo),
// there MUST be at least one safe bit in range [0..15].
int target_safe = -1;
for(int i = 0; i <= 15; i++) {
if(!C[i]) {
target_safe = i;
break;
}
}
// ---------------------------------------------------------
// PHASE 1: Binary Search (4 iterations)
// ---------------------------------------------------------
// Search Range starts at [0, 15]
int bs_L = 0;
int bs_R = 15;
for (int iter = 0; iter < 4; iter++) {
vector<bool> packet(31, 0);
int mid = bs_L + (bs_R - bs_L) / 2;
// Define halves
// Left: [bs_L, mid], Right: [mid+1, bs_R]
// Sender Logic:
// If target is in Left, light up SAFE bits in Left.
// If target is in Right, light up SAFE bits in Right.
bool go_right = (target_safe > mid);
for (int i = 0; i < 31; i++) {
bool in_current_bs_range = (i >= bs_L && i <= bs_R);
if (in_current_bs_range) {
// We are inside the active comparison zone.
// We only light up the side where the target is.
bool in_left_half = (i <= mid);
bool in_right_half = (i > mid);
if (!go_right && in_left_half) {
// Target is left, we are in left. Send 1 if safe.
if (!C[i]) packet[i] = 1;
} else if (go_right && in_right_half) {
// Target is right, we are in right. Send 1 if safe.
if (!C[i]) packet[i] = 1;
}
// Else: we are in the "wrong" half or it's a Cleo bit.
// We send 0 (Sender preference).
} else {
// "Use every bit that is both safe and not in the binary search range"
// This includes bits 16-30 and bits discarded in previous BS steps.
if (!C[i] && msg_ptr < S) {
packet[i] = M[msg_ptr++];
}
}
}
send_packet(packet);
// Update Sender's view of BS state for next iteration
if (!go_right) bs_R = mid;
else bs_L = mid + 1;
}
// ---------------------------------------------------------
// PHASE 2: Map Discovery (30 Packets)
// ---------------------------------------------------------
// target_safe tells us the state of the other 30 bits.
vector<int> map_targets;
for(int i=0; i<31; i++) {
if(i != target_safe) map_targets.push_back(i);
}
for (int i = 0; i < 30; i++) {
vector<bool> packet(31, 0);
int index_to_report = map_targets[i];
// Signaling bit
packet[target_safe] = !C[index_to_report]; // 1 if Safe, 0 if Corrupt
// Message bits (All other safe bits)
for (int j = 0; j < 31; j++) {
if (j == target_safe) continue;
if (!C[j] && msg_ptr < S) {
packet[j] = M[msg_ptr++];
}
}
send_packet(packet);
}
// ---------------------------------------------------------
// PHASE 3: Flush Remaining Message
// ---------------------------------------------------------
while (msg_ptr < S) {
vector<bool> packet(31, 0);
for(int j=0; j<31; j++) {
if (!C[j] && msg_ptr < S) {
packet[j] = M[msg_ptr++];
}
}
send_packet(packet);
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
// We need to look back in time, so we process R in multiple passes.
vector<bool> M;
// ---------------------------------------------------------
// Step 1: Replay Binary Search to find the Safe Bit
// ---------------------------------------------------------
int bs_L = 0;
int bs_R = 15;
for (int iter = 0; iter < 4; iter++) {
int mid = bs_L + (bs_R - bs_L) / 2;
// Count 1s in the Left Half vs Right Half
int sum_left = 0;
int sum_right = 0;
for (int i = bs_L; i <= mid; i++) {
if (R[iter][i]) sum_left++;
}
for (int i = mid + 1; i <= bs_R; i++) {
if (R[iter][i]) sum_right++;
}
// "See which one has the majority and go into that part"
if (sum_left > sum_right) {
bs_R = mid;
} else {
bs_L = mid + 1;
}
}
int primary_safe = bs_L;
// ---------------------------------------------------------
// Step 2: Build the Safe Map
// ---------------------------------------------------------
vector<bool> is_safe(31, false);
is_safe[primary_safe] = true;
vector<int> map_targets;
for(int i=0; i<31; i++) {
if(i != primary_safe) map_targets.push_back(i);
}
for (int i = 0; i < 30; i++) {
// Read the signal from the known safe bit
bool info = R[4 + i][primary_safe];
int index_being_reported = map_targets[i];
is_safe[index_being_reported] = info;
}
// ---------------------------------------------------------
// Step 3: Extract Message (Time Travel)
// ---------------------------------------------------------
// 3a. From BS Phase (Packets 0-3)
bs_L = 0; bs_R = 15;
for (int iter = 0; iter < 4; iter++) {
// Extract message from bits NOT in current BS range
for (int j = 0; j < 31; j++) {
bool in_range = (j >= bs_L && j <= bs_R);
if (!in_range && is_safe[j]) {
M.push_back(R[iter][j]);
}
}
// Re-calculate BS step to know the range for the *next* iteration
int mid = bs_L + (bs_R - bs_L) / 2;
int sum_left = 0;
int sum_right = 0;
for (int i = bs_L; i <= mid; i++) if (R[iter][i]) sum_left++;
for (int i = mid + 1; i <= bs_R; i++) if (R[iter][i]) sum_right++;
if (sum_left > sum_right) bs_R = mid;
else bs_L = mid + 1;
}
// 3b. From Map Phase (Packets 4-33)
for (int i = 0; i < 30; i++) {
for (int j = 0; j < 31; j++) {
if (j == primary_safe) continue; // This was used for signaling
if (is_safe[j]) {
M.push_back(R[4 + i][j]);
}
}
}
// 3c. From Flush Phase (Packets 34+)
for (int p = 34; p < R.size(); p++) {
for (int j = 0; j < 31; j++) {
if (is_safe[j]) {
M.push_back(R[p][j]);
}
}
}
return M;
}
