Submission #1291993

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

message

#include <vector>
#include <cstddef>
#include <algorithm>
#include "message.h"
// Provided elsewhere:
// 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 inline std::vector<int> get_uncontrolled_indices(const std::vector<bool>& C_like) {
    std::vector<int> idx;
    idx.reserve(C_like.size());
    for (int i = 0; i < static_cast<int>(C_like.size()); ++i) {
        if (!C_like[i]) idx.push_back(i);
    }
    return idx;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
    // Python: S = len(M), n = (S + 15) // 16
    const int S = static_cast<int>(M.size());
    const int n = (S + 15) / 16;

    // First 16 packets: encode controlled indices (C[i] == 1) as non-constant across these packets.
    for (int j = 0; j < 16; ++j) {
        std::vector<bool> A(31, false);
        for (int i = 0; i < 31; ++i) {
            if (!C[i]) {
                A[i] = false;
            } else {
                A[i] = (j % 2) != 0; // toggles so it's not constant
            }
        }
        (void)send_packet(A);
    }

    // Uncontrolled indices (C[i] == 0)
    std::vector<int> uncontrolled_indices = get_uncontrolled_indices(C);

    // Encode S as a 16-bit big-endian binary across uncontrolled indices
    // Equivalent to Python's left-padded bin string.
    std::vector<bool> A_S(31, false);
    for (int idx = 0; idx < 16; ++idx) {
        int bit_index_from_msb = 15 - idx;
        bool bit = ((S >> bit_index_from_msb) & 1) != 0;
        int i = uncontrolled_indices[idx];
        A_S[i] = bit;
    }
    (void)send_packet(A_S);

    // Pad message M to multiple of 16
    std::vector<bool> padded_M = M;
    padded_M.resize(16 * n, false);

    // Send n chunks of 16 bits across uncontrolled indices
    for (int t = 0; t < n; ++t) {
        std::vector<bool> A(31, false);
        int start = t * 16;
        for (int idx = 0; idx < 16; ++idx) {
            int i = uncontrolled_indices[idx];
            A[i] = padded_M[start + idx];
        }
        (void)send_packet(A);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    // Recover C by checking constancy across first 16 packets
    std::vector<bool> C_recovered(31, false);
    for (int i = 0; i < 31; ++i) {
        bool constant = true;
        if (R.size() >= 1) {
            bool first = (R.size() >= 1 && R[0].size() > static_cast<size_t>(i)) ? R[0][i] : false;
            for (size_t p = 1; p < std::min<size_t>(16, R.size()); ++p) {
                bool b = (R[p].size() > static_cast<size_t>(i)) ? R[p][i] : false;
                if (b != first) {
                    constant = false;
                    break;
                }
            }
        }
        // If not constant -> controlled -> 1, else 0
        C_recovered[i] = !constant;
    }

    // Uncontrolled indices (where recovered C is 0)
    std::vector<int> uncontrolled_indices = get_uncontrolled_indices(C_recovered);

    // Read S from packet R[16] over the first 16 uncontrolled indices (MSB first)
    int S_val = 0;
    if (R.size() > 16) {
        const std::vector<bool>& pkt_len = R[16];
        for (int idx = 0; idx < 16; ++idx) {
            int col = uncontrolled_indices[idx];
            bool bit = (pkt_len.size() > static_cast<size_t>(col)) ? pkt_len[col] : false;
            S_val = (S_val << 1) | (bit ? 1 : 0);
        }
    } else {
        // If length packet missing, S_val remains 0 -> empty message
        return {};
    }

    const int n = (S_val + 15) / 16;

    // Collect message bits from packets 17 .. 17 + n - 1
    std::vector<bool> message_bits;
    message_bits.reserve(static_cast<size_t>(S_val));
    for (int t = 17; t < 17 + n; ++t) {
        if (t >= static_cast<int>(R.size())) break;
        const std::vector<bool>& packet = R[t];
        for (int col : uncontrolled_indices) {
            if (static_cast<size_t>(col) < packet.size()) {
                message_bits.push_back(packet[col]);
            }
        }
    }

    // Truncate to S_val bits
    if (static_cast<int>(message_bits.size()) > S_val) {
        message_bits.resize(S_val);
    }

    return message_bits;
}

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