Submission #1296313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296313		NotLinux	Message (IOI24_message)	C++20	0 / 100	178 ms	800 KiB

message

#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;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 90