Submission #1236915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236915		hugo_pm	Message (IOI24_message)	C++20	76.16 / 100	398 ms	852 KiB

message

#include "message.h"
#include <cassert>
#include <iostream>
using namespace std;

constexpr int PACKET_SIZE = 31, LOG_P_SIZE = 5;
constexpr int LOG_MAX_MSG_SIZE_MINUS_ONE = 10;

void send_message(vector<bool> msg, vector<bool> controlled) {
    int witness_bit = 0, size_msg = msg.size();
    while (controlled[witness_bit])
        ++witness_bit;
    for (int i_pw = 0; i_pw < LOG_P_SIZE; ++i_pw) {
        bool val = (witness_bit >> i_pw) & 1;
        send_packet(vector<bool>(PACKET_SIZE, val));
    }
    vector<int> avail;
    for (int i_bit = 0; i_bit < PACKET_SIZE; ++i_bit) {
        if (!controlled[i_bit] && i_bit != witness_bit)
            avail.push_back(i_bit);
    }
    vector<bool> testimonies;
    for (bool ctr : controlled)
        testimonies.push_back(ctr); // wasting 1 bit for controlled[witness]
    for (int i_pw = 0; i_pw < LOG_MAX_MSG_SIZE_MINUS_ONE; ++i_pw) {
        bool val = ((size_msg-1) >> i_pw) & 1;
        testimonies.push_back(val);
    }
    int nb_testimonies = testimonies.size();
    int next_msg_bit = 0, next_testimony = 0;
    while (next_msg_bit < (int)msg.size() || next_testimony < nb_testimonies) {
        vector<bool> packet(PACKET_SIZE);
        if (next_testimony < nb_testimonies) {
            packet[witness_bit] = testimonies[next_testimony++];
        } else if (avail.back() != witness_bit) {
            avail.push_back(witness_bit);
        }
        for (int bit : avail) {
            if (next_msg_bit < (int)msg.size()) {
                packet[bit] = msg[next_msg_bit++];
            }
        }
        send_packet(packet);
    }
}

bool maj_element(vector<bool> &a) {
    int cnt = count(a.begin(), a.end(), true);
    return 2*cnt >= (int)a.size();
}

vector<bool> receive_message(vector<vector<bool>> packets) {
    int witness_bit = 0;
    for (int i_pack = 0; i_pack < LOG_P_SIZE; ++i_pack) {
        if (maj_element(packets[i_pack]))
            witness_bit += (1 << i_pack);
    }
    packets.erase(packets.begin(), packets.begin() + LOG_P_SIZE);
    vector<int> avail;
    for (int i_packet = 0; i_packet < PACKET_SIZE; ++i_packet) {
        int observed_bit = i_packet; // small waste
        bool control = packets[i_packet][witness_bit];
        if (!control && observed_bit != witness_bit) // not controlled
            avail.push_back(observed_bit);
    }
    int size_msg = 1; // then add binary encoding of size-1
    for (int delta = 0; delta < LOG_MAX_MSG_SIZE_MINUS_ONE; ++delta) {
        int i_pack = PACKET_SIZE+delta;
        if (packets[i_pack][witness_bit])
            size_msg += (1 << delta);
    }
    vector<bool> msg;
    for (int i_packet = 0; i_packet < (int)packets.size(); ++i_packet) {
        if (i_packet == PACKET_SIZE + LOG_MAX_MSG_SIZE_MINUS_ONE)
            avail.push_back(witness_bit);
        for (int bit : avail) if ((int)msg.size() < size_msg) {
            msg.push_back(packets[i_packet][bit]);
        }
    }
    return msg;
}

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