Submission #1291793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291793		lucas110550	Message (IOI24_message)	C++20	0 / 100	38 ms	780 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> compute_fixed_indices_from_C(const std::vector<bool>& C) {
    std::vector<int> fixed_indices;
    fixed_indices.reserve(31);
    for (int i = 0; i < 31 && i < static_cast<int>(C.size()); ++i) {
        if (!C[i]) fixed_indices.push_back(i);
    }
    std::sort(fixed_indices.begin(), fixed_indices.end());
    return fixed_indices;
}

void send_message(std::vector<bool> M, std::vector<bool> C) {
    const int S = static_cast<int>(M.size());
    const int P = (S + 15) / 16; // Number of message packets

    // Determine fixed indices from C (positions where C[i] == 0)
    std::vector<int> fixed_indices = compute_fixed_indices_from_C(C);

    // Safety: ensure we have at least 16 positions to place data bits
    if (static_cast<int>(fixed_indices.size()) < 16) {
        // Nothing sensible to do; mimic Python behavior would likely throw later.
        // Here we simply return.
        return;
    }

    // Send P data packets
    for (int k = 0; k < P; ++k) {
        std::vector<bool> packet(31, false);
        int start = 16 * k;
        for (int j = 0; j < 16; ++j) {
            int pos = start + j;
            bool bit = (pos < S) ? M[pos] : false;
            int idx = fixed_indices[j];
            if (idx >= 0 && idx < 31) packet[idx] = bit;
        }
        (void)send_packet(packet); // return value intentionally ignored (as in Python)
    }

    // Send packet0: S in first 11 fixed slots, then ones in slots 11..15
    {
        std::vector<bool> packet0(31, false);
        for (int j = 0; j < 11; ++j) {
            int idx = fixed_indices[j];
            if (idx >= 0 && idx < 31) {
                bool bit = ((S >> j) & 1) != 0;
                packet0[idx] = bit;
            }
        }
        for (int j = 11; j < 16; ++j) {
            int idx = fixed_indices[j];
            if (idx >= 0 && idx < 31) packet0[idx] = true;
        }
        (void)send_packet(packet0);
    }

    // Send packet1: inverted S in first 11 fixed slots, then zeros in slots 11..15
    {
        std::vector<bool> packet1(31, false);
        for (int j = 0; j < 11; ++j) {
            int idx = fixed_indices[j];
            if (idx >= 0 && idx < 31) {
                bool bit = ((S >> j) & 1) != 0;
                packet1[idx] = !bit;
            }
        }
        for (int j = 11; j < 16; ++j) {
            int idx = fixed_indices[j];
            if (idx >= 0 && idx < 31) packet1[idx] = false;
        }
        (void)send_packet(packet1);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    std::vector<bool> M;

    if (R.size() < 2) {
        return M; // Not enough packets to recover length
    }

    const std::vector<bool>& extra0 = R[R.size() - 2];
    const std::vector<bool>& extra1 = R[R.size() - 1];

    // Reconstruct fixed indices: positions where extra0[i] != extra1[i]
    std::vector<int> fixed_indices;
    fixed_indices.reserve(31);
    for (int i = 0; i < 31; ++i) {
        bool a = (i < static_cast<int>(extra0.size())) ? extra0[i] : false;
        bool b = (i < static_cast<int>(extra1.size())) ? extra1[i] : false;
        if (a != b) fixed_indices.push_back(i);
    }
    std::sort(fixed_indices.begin(), fixed_indices.end());

    // Reconstruct S from first up-to-11 fixed slots in extra0
    int S = 0;
    for (int j = 0; j < 11 && j < static_cast<int>(fixed_indices.size()); ++j) {
        int idx = fixed_indices[j];
        if (idx >= 0 && idx < static_cast<int>(extra0.size())) {
            bool bit = extra0[idx];
            if (bit) S |= (1 << j);
        }
    }

    const int P = (S + 15) / 16;

    // Extract bits across up to P packets, honoring bounds like Python
    for (int k = 0; k < P && k < static_cast<int>(R.size()); ++k) {
        const std::vector<bool>& packet = R[k];
        int start = 16 * k;
        if (start >= S) break;

        for (int j = 0; j < 16 && (start + j) < S; ++j) {
            int idx = (j < static_cast<int>(fixed_indices.size())) ? fixed_indices[j] : -1;
            if (idx >= 0 && idx < static_cast<int>(packet.size())) {
                M.push_back(packet[idx]);
            } else {
                // If index is missing, push a default (Python would have errored; we degrade gracefully)
                M.push_back(false);
            }
        }
    }

    return M;
}

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