Submission #1295854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295854		lucas110550	Message (IOI24_message)	C++20	29.32 / 100	541 ms	804 KiB

message

#include <vector>
#include <algorithm>
#include <cstdint>
#include "message.h"

void send_message(std::vector<bool> M, std::vector<bool> C) {
    int S = M.size();
    // Prepend 11-bit representation of S (big-endian)
    std::vector<bool> M_padded;
    for (int i = 10; i >= 0; i--) {
        M_padded.push_back((S >> i) & 1);
    }
    for (bool b : M) {
        M_padded.push_back(b);
    }
    int total_bits = M_padded.size();
    int D = (total_bits + 15) / 16; // ceil division

    // Pad to D*16 bits
    M_padded.resize(D * 16, false);

    // Send pattern: 31 packets
    for (int i = 0; i < 31; i++) {
        std::vector<bool> packet(31, C[i]); // if C[i] is true, then all ones; else all zeros.
        send_packet(packet);
    }

    // Get safe indices (where C[j] is false) and sort
    std::vector<int> safe_indices;
    for (int j = 0; j < 31; j++) {
        if (!C[j]) {
            safe_indices.push_back(j);
        }
    }
    std::sort(safe_indices.begin(), safe_indices.end());

    // Send data packets
    for (int i = 0; i < D; i++) {
        std::vector<bool> packet(31, false); // all zeros by default
        for (int j = 0; j < 16; j++) {
            int idx = safe_indices[j];
            packet[idx] = M_padded[i * 16 + j];
        }
        send_packet(packet);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    int num_packets = R.size();
    if (num_packets < 31) {
        // Not enough packets, return empty
        return std::vector<bool>();
    }

    // Reconstruct C_recv from the first 31 packets
    std::vector<bool> C_recv(31, false);
    for (int i = 0; i < 31; i++) {
        const std::vector<bool>& pkt = R[i];
        int cnt = 0;
        for (bool b : pkt) {
            if (b) cnt++;
        }
        C_recv[i] = (cnt >= 16); // if at least 16 ones, then true (1)
    }

    // Get safe indices from C_recv (where it is false) and sort
    std::vector<int> safe_indices;
    for (int j = 0; j < 31; j++) {
        if (!C_recv[j]) {
            safe_indices.push_back(j);
        }
    }
    std::sort(safe_indices.begin(), safe_indices.end());

    int D = num_packets - 31; // number of data packets
    std::vector<bool> M_total;
    for (int i = 31; i < num_packets; i++) {
        const std::vector<bool>& pkt = R[i];
        for (int j = 0; j < safe_indices.size(); j++) {
            int idx = safe_indices[j];
            M_total.push_back(pkt[idx]);
        }
    }

    // If we don't have at least 11 bits, return empty
    if (M_total.size() < 11) {
        return std::vector<bool>();
    }

    // Decode the length (first 11 bits, big-endian)
    int len = 0;
    for (int i = 0; i < 11; i++) {
        len = (len << 1) | (M_total[i] ? 1 : 0);
    }

    // Check if we have enough bits for the message
    if (M_total.size() < 11 + len) {
        // Not enough, return empty
        return std::vector<bool>();
    }

    // Extract the message
    std::vector<bool> message;
    for (int i = 0; i < len; i++) {
        message.push_back(M_total[11 + i]);
    }
    return message;
}

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