Submission #1296668

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

message

#include <vector>
#include <algorithm>
#include <string>
#include "message.h"
using std::vector;
using std::string;


void send_message(vector<bool> M, vector<bool> C) {
    // Find safe indices (positions where C[j] == 0)
    vector<int> safe_indices;
    for (int j = 0; j < 31; ++j) {
        if (C[j] == false) {
            safe_indices.push_back(j);
        }
    }
    std::sort(safe_indices.begin(), safe_indices.end());

    // First 31 packets: repetition of each bit of C on safe positions
    for (int i = 0; i < 31; ++i) {
        vector<bool> A(31, false);
        for (int idx : safe_indices) {
            A[idx] = C[i];
        }
        send_packet(A);
    }

    // Encode length S_val of message M using 11 bits
    int S_val = static_cast<int>(M.size());

    // Convert S_val to binary string without leading zeros
    string bin_S;
    if (S_val == 0) {
        bin_S = "0";
    } else {
        int tmp = S_val;
        while (tmp > 0) {
            bin_S.push_back((tmp % 2) + '0');
            tmp /= 2;
        }
        std::reverse(bin_S.begin(), bin_S.end());
    }

    // Left-pad to 11 bits if needed
    if (static_cast<int>(bin_S.size()) < 11) {
        bin_S = string(11 - bin_S.size(), '0') + bin_S;
    }

    // Send S_val encoded on safe_indices[:11]
    {
        vector<bool> A(31, false);
        for (int k = 0; k < 11; ++k) {
            A[safe_indices[k]] = (bin_S[k] == '1');
        }
        send_packet(A);
    }

    // Split M into chunks of up to 16 bits and send them
    int n_chunks = (S_val + 15) / 16;
    int start = 0;
    for (int chunk_idx = 0; chunk_idx < n_chunks; ++chunk_idx) {
        int end = start + 16;
        if (end > S_val) {
            end = S_val;
        }
        int L = end - start;

        vector<bool> A(31, false);
        for (int k = 0; k < L; ++k) {
            A[safe_indices[k]] = M[start + k];
        }
        send_packet(A);

        start = end;
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    // Majority-vote decode of C from the first 31 packets
    vector<int> received_C(31, 0);
    for (int p = 0; p < 31; ++p) {
        const vector<bool>& packet = R[p];
        int count0 = 0, count1 = 0;
        for (bool bit : packet) {
            if (bit == false) {
                ++count0;
            } else {
                ++count1;
            }
        }
        received_C[p] = (count1 > count0) ? 1 : 0;
    }

    // Compute safe indices from received_C
    vector<int> safe_indices;
    for (int j = 0; j < 31; ++j) {
        if (received_C[j] == 0) {
            safe_indices.push_back(j);
        }
    }
    std::sort(safe_indices.begin(), safe_indices.end());

    // Decode S_val (message length) from packet R[31] on safe_indices[:11]
    const vector<bool>& packet_S = R[31];
    vector<int> S_bits;
    for (int k = 0; k < 11 && k < static_cast<int>(safe_indices.size()); ++k) {
        int j = safe_indices[k];
        S_bits.push_back(packet_S[j] ? 1 : 0);
    }

    int S_val = 0;
    for (int b : S_bits) {
        S_val = (S_val << 1) | b;
    }

    int n_chunks = (S_val + 15) / 16;
    vector<bool> message;

    // Decode chunks from packets R[32 .. 32 + n_chunks - 1]
    for (int i = 32; i < 32 + n_chunks && i < static_cast<int>(R.size()); ++i) {
        const vector<bool>& packet = R[i];

        if (i == 32 + n_chunks - 1) {
            // Last chunk may be partial
            int L = S_val - 16 * (n_chunks - 1);
            for (int k = 0; k < L && k < static_cast<int>(safe_indices.size()); ++k) {
                int j = safe_indices[k];
                message.push_back(packet[j]);
            }
        } else {
            // Full chunk
            for (int idx : safe_indices) {
                message.push_back(packet[idx]);
            }
        }
    }

    return message;
}

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