Submission #1292005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292005		lucas110550	Message (IOI24_message)	C++20	0 / 100	113 ms	772 KiB

message

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

// Convert and send
void send_message(std::vector<bool> M, std::vector<bool> C) {
    const int S = static_cast<int>(M.size());
    const int WIDTH = 31;

    if (S == 0) {
        // Send 16 zero packets
        for (int _ = 0; _ < 16; ++_) {
            send_packet(std::vector<bool>(WIDTH, false));
        }
        return;
    }

    // U = indices where C[i] == 0
    std::vector<int> U;
    U.reserve(WIDTH);
    for (int i = 0; i < WIDTH && i < static_cast<int>(C.size()); ++i) {
        if (!C[i]) U.push_back(i);
    }

    // n = 1 + (S + 10) // 16
    const int n = 1 + (S + 10) / 16;

    // Preamble: 16 packets where A[U[*]] = (k & 1)
    for (int k = 0; k < 16; ++k) {
        std::vector<bool> A(WIDTH, false);
        for (int idx : U) {
            if (idx >= 0 && idx < WIDTH) {
                A[idx] = static_cast<bool>(k & 1);
            }
        }
        (void)send_packet(std::vector<bool>(A));
    }

    // Packet #16: 11-bit length (MSB first), then up to first 5 bits of message
    int ptr = 0;

    std::vector<bool> A(WIDTH, false);
    // Place 11 MSB-first bits of S into A[U[0..10]]
    for (int i = 0; i < 11; ++i) {
        if (i < static_cast<int>(U.size())) {
            int bit = (S >> (10 - i)) & 1;
            int idx = U[i];
            if (idx >= 0 && idx < WIDTH) A[idx] = static_cast<bool>(bit);
        }
    }

    // Then up to 5 message bits next at U[11..15]
    int num_first_bits = std::min(5, S);
    for (int i = 11; i < 11 + num_first_bits; ++i) {
        if (i < static_cast<int>(U.size()) && ptr < S) {
            int idx = U[i];
            if (idx >= 0 && idx < WIDTH) A[idx] = M[ptr];
            ++ptr;
        }
    }
    (void)send_packet(std::vector<bool>(A));

    // Subsequent packets: fill up to 16 bits each at U[0..15]
    for (int k = 17; k < 16 + n; ++k) {
        std::vector<bool> B(WIDTH, false);
        for (int i = 0; i < 16 && i < static_cast<int>(U.size()); ++i) {
            if (ptr >= S) break;
            int idx = U[i];
            if (idx >= 0 && idx < WIDTH) B[idx] = M[ptr];
            ++ptr;
        }
        (void)send_packet(std::vector<bool>(B));
    }
}

// Receive and reconstruct
std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    const int WIDTH = 31;

    // Identify usable indices U by checking the 16-packet preamble pattern
    std::vector<int> U;
    U.reserve(WIDTH);
    for (int i = 0; i < WIDTH; ++i) {
        bool valid = true;
        if (static_cast<int>(R.size()) < 16) { valid = false; }
        else {
            for (int k = 0; k < 16; ++k) {
                if (i >= static_cast<int>(R[k].size())) { valid = false; break; }
                bool expected = static_cast<bool>(k & 1);
                if (R[k][i] != expected) { valid = false; break; }
            }
        }
        if (valid) U.push_back(i);
    }

    if (U.empty()) return {};           // No valid columns
    if (static_cast<int>(R.size()) < 16) return {}; // Not enough preamble packets

    // Extract S from packet #16 (index 16), MSB-first across U[0..10]
    int S = 0;
    if (static_cast<int>(R.size()) >= 17) {
        // We have packet 16 (0-based index)
        for (int i = 0; i < 11; ++i) {
            int bit = 0;
            if (i < static_cast<int>(U.size())) {
                int idx = U[i];
                if (idx >= 0 && idx < static_cast<int>(R[16].size()))
                    bit = R[16][idx] ? 1 : 0;
            }
            S = (S << 1) | bit;
        }
    } else {
        // Defensive: if somehow there's no packet 16, S remains 0
        S = 0;
    }

    std::vector<bool> M_recovered;
    M_recovered.reserve(S);
    int count = 0;

    if (static_cast<int>(R.size()) > 16) {
        // Read up to 5 bits embedded in packet #16 after the 11-bit length
        const auto& first_msg_packet = R[16];
        int num_first_bits = std::min(5, S);
        for (int i = 11; i < 11 + num_first_bits; ++i) {
            if (i < static_cast<int>(U.size()) && count < S) {
                int idx = U[i];
                if (idx >= 0 && idx < static_cast<int>(first_msg_packet.size())) {
                    bool bit_val = first_msg_packet[idx];
                    M_recovered.push_back(bit_val);
                    ++count;
                }
            }
        }
        // Read remaining bits from packets #17..end, positions U[0..15]
        for (int j = 17; j < static_cast<int>(R.size()); ++j) {
            if (count >= S) break;
            const auto& packet = R[j];
            for (int i = 0; i < 16 && i < static_cast<int>(U.size()); ++i) {
                if (count >= S) break;
                int idx = U[i];
                if (idx >= 0 && idx < static_cast<int>(packet.size())) {
                    bool bit_val = packet[idx];
                    M_recovered.push_back(bit_val);
                    ++count;
                }
            }
        }
    } else {
        // Fallback path from the original Python (rare): try to read straight from packet #16
        if (S > 0 && static_cast<int>(R.size()) >= 17) {
            for (int i = 11; i < 11 + S; ++i) {
                if (i < static_cast<int>(U.size())) {
                    int idx = U[i];
                    if (idx >= 0 && idx < static_cast<int>(R[16].size())) {
                        bool bit_val = R[16][idx];
                        M_recovered.push_back(bit_val);
                        ++count;
                    }
                }
            }
        }
    }

    // Pad with zeros if we couldn't recover all bits
    while (count < S) {
        M_recovered.push_back(false);
        ++count;
    }

    return M_recovered;
}

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