Submission #1292007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292007		lucas110550	메시지 (IOI24_message)	C++20	0 / 100	112 ms	744 KiB

message

#include <vector>
#include <algorithm>
#include <cstddef>
#include "message.h"
// Provided elsewhere:
// std::vector<bool> send_packet(std::vector<bool> A);

// Send M using constraint mask C (31 bits). C[i] == 0 means that bit position i is usable.
void send_message(std::vector<bool> M, std::vector<bool> C) {
    const int S = static_cast<int>(M.size());

    // Build list of free positions F (where C[i] == 0) among 31 columns
    std::vector<int> F;
    F.reserve(31);
    for (int i = 0; i < 31; ++i) {
        if (i < static_cast<int>(C.size()) && C[i] == false) {
            F.push_back(i);
        }
    }
    std::sort(F.begin(), F.end());

    // Number of packets: 16 sync + 1 size + ceil(S/16) payload packets
    const int n = 16 + 1 + ((S + 15) / 16);

    // 16 synchronization packets: column i carries pattern j % 2
    for (int j = 0; j < 16; ++j) {
        std::vector<bool> packet(31, (j % 2) != 0);
        (void)send_packet(packet);
    }

    // One packet carrying 11 MSB-first bits of S in the first 11 free positions
    std::vector<bool> packet_S(31, false);
    for (int i = 0; i < 11; ++i) {
        // mirror Python's assumption that F has at least 11 positions
        int bit = (S >> (10 - i)) & 1;
        packet_S[F[i]] = (bit != 0);
    }
    (void)send_packet(packet_S);

    // Payload packets: up to 16 data bits per packet, mapped to F[0..]
    int start = 0;
    for (int k = 17; k < n; ++k) {
        std::vector<bool> packet(31, false);
        int num_bits = std::min(16, S - start);
        for (int i = 0; i < num_bits; ++i) {
            // mirror Python's assumption that F has at least 16 positions
            packet[F[i]] = M[start + i];
        }
        (void)send_packet(packet);
        start += num_bits;
    }
}

// Recover message bits from received packets R
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    // Need at least the 16 sync packets + 1 size packet
    if (R.size() < 17) {
        return {};
    }

    // Determine free positions F by checking the 16 sync packets pattern j % 2
    std::vector<int> F;
    F.reserve(31);
    for (int i = 0; i < 31; ++i) {
        bool valid = true;
        for (int j = 0; j < 16; ++j) {
            // Defensive bounds checks for robustness
            if (i >= static_cast<int>(R[j].size()) || R[j][i] != ((j % 2) != 0)) {
                valid = false;
                break;
            }
        }
        if (valid) F.push_back(i);
    }
    std::sort(F.begin(), F.end());

    // Read 11-bit size field from packet 17 (index 16), limited by |F|
    const std::vector<bool>& packet17 = R[16];
    int num_fixed = std::min(11, static_cast<int>(F.size()));
    std::vector<int> bits;
    bits.reserve(num_fixed);
    for (int i = 0; i < num_fixed; ++i) {
        bits.push_back(packet17[F[i]] ? 1 : 0);
    }

    // Assemble S from MSB-first bits
    int S = 0;
    for (int bit : bits) {
        S = (S << 1) | bit;
    }

    // Extract payload from subsequent packets, up to S bits
    std::vector<bool> M_recovered;
    M_recovered.reserve(static_cast<size_t>(S));
    int start = 0;
    for (size_t k = 17; k < R.size(); ++k) {
        if (start >= S) break;
        const std::vector<bool>& packet = R[k];
        int num_bits = std::min(16, S - start);
        for (int i = 0; i < num_bits; ++i) {
            if (start >= S) break;
            // mirror Python: take packet[F[i]] for i in [0, num_bits)
            M_recovered.push_back(packet[F[i]]);
            ++start;
        }
    }

    return M_recovered;
}

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