Submission #1291954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291954		lucas110550	Message (IOI24_message)	C++20	0 / 100	39 ms	724 KiB

message

#include <vector>
#include <algorithm>
#include <cstdint>
#include "message.h"
// Given signatures:
// void send_message(std::vector<bool> M, std::vector<bool> C)
// std::vector<bool> send_packet(std::vector<bool> A)
// std::vector<bool> receive_message(std::vector<std::vector<bool>> R)

static std::vector<bool> intToBits(unsigned int value, int width) {
    std::vector<bool> bits(width, false);
    for (int i = 0; i < width; ++i) {
        // Fill MSB-first (bits[0] is the most-significant bit)
        bits[width - 1 - i] = (value & 1u);
        value >>= 1u;
    }
    return bits;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
    const int N = 31;
    const int HEADER_BITS = 11;

    // S = len(M)
    unsigned int S = static_cast<unsigned int>(M.size());

    // U = sorted indices i in [0..30] where C[i] == 0
    std::vector<int> U;
    U.reserve(N);
    for (int i = 0; i < N; ++i) {
        if (C[i] == false) U.push_back(i);
    }
    std::sort(U.begin(), U.end());

    // Build a position lookup: pos[i] = index of i in U, or -1 if not in U
    std::vector<int> pos(N, -1);
    for (int j = 0; j < (int)U.size(); ++j) pos[U[j]] = j;

    // s_bits = 11-bit MSB-first representation of S (zero-padded)
    std::vector<bool> s_bits = intToBits(S, HEADER_BITS);

    // Send two header packets
    for (int rep = 0; rep < 2; ++rep) {
        std::vector<bool> A(N, false);
        for (int i = 0; i < N; ++i) {
            if (C[i] == true) {
                A[i] = true;
            } else {
                int j = pos[i];  // equivalent to Python's j = U.index(i)
                if (j >= 0 && j < HEADER_BITS) {
                    A[i] = s_bits[j];
                } else {
                    A[i] = false;
                }
            }
        }
        (void)send_packet(A); // ignore returned value to mirror Python behavior
    }

    // Send payload packets with up to 16 bits each
    int num_msg = (S + 15) / 16;
    for (int p = 0; p < num_msg; ++p) {
        int start = p * 16;
        int end = std::min<int>(S, start + 16);
        std::vector<bool> A(N, false);

        // Fill only up to min(#bits in this chunk, |U|)
        int chunk_len = end - start;
        int limit = std::min<int>(chunk_len, (int)U.size());
        for (int k = 0; k < limit; ++k) {
            int idx = U[k];
            A[idx] = M[start + k];
        }
        (void)send_packet(A);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    const int N = 31;
    const int HEADER_BITS = 11;

    // U = indices i where R[0][i] == R[1][i], sorted
    std::vector<int> U;
    U.reserve(N);
    if (R.size() >= 2) {
        for (int i = 0; i < N; ++i) {
            if (R[0][i] == R[1][i]) U.push_back(i);
        }
    }
    std::sort(U.begin(), U.end());

    // Extract 11 header bits (or zeros if fewer than 11 U)
    std::vector<bool> s_bits(HEADER_BITS, false);
    if ((int)U.size() >= HEADER_BITS) {
        for (int b = 0; b < HEADER_BITS; ++b) {
            s_bits[b] = R[0][U[b]];
        }
    }
    // Convert MSB-first bits to integer
    unsigned int S_val = 0;
    for (int b = 0; b < HEADER_BITS; ++b) {
        S_val = (S_val << 1u) | (s_bits[b] ? 1u : 0u);
    }

    int num_msg = (S_val + 15) / 16;
    std::vector<bool> M;
    M.reserve(S_val);

    // Read payload packets R[2] .. R[2 + num_msg - 1]
    for (int p = 2; p < 2 + num_msg && p < (int)R.size(); ++p) {
        const std::vector<bool>& packet = R[p];
        int remaining = (int)S_val - (int)M.size();
        if (remaining <= 0) break;

        // Only read as many bits as both the packet chunk (<=16), remaining, and |U|
        int take = std::min<int>({16, remaining, (int)U.size()});
        for (int k = 0; k < take; ++k) {
            bool bit = packet[U[k]];
            M.push_back(bit);
        }
    }

    // Truncate to exactly S_val in case of any over-reads (defensive)
    if ((int)M.size() > (int)S_val) M.resize(S_val);
    return M;
}

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