Submission #1267383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267383		alphabeastmam	Message (IOI24_message)	C++17	10 / 100	514 ms	844 KiB

message

#include <bits/stdc++.h>
using namespace std;

/*
   The grader provides send_packet() in the sender program.
   On the receiver side, only receive_message() is called.
*/

// ================= SENDER SIDE =================

// This will be provided by the grader in the sender program.
// We declare it here so the code compiles.
extern vector<bool> send_packet(vector<bool> A);

// Encode message length S (<= 1024) into 10 bits, MSB first.
static vector<bool> encode_len10(int S) {
    vector<bool> bits(10, false);
    for (int i = 9; i >= 0; --i) {
        bits[9 - i] = ((S >> i) & 1);
    }
    return bits;
}

void send_message(vector<bool> M, vector<bool> C) {
    // Build mask G of reliable indices: 1 = reliable, 0 = controlled
    vector<bool> G(31, false);
    for (int i = 0; i < 31; ++i) G[i] = !C[i];

    // === Phase 1: Send 31 cyclic shifts of G ===
    for (int t = 0; t < 31; ++t) {
        vector<bool> A(31, false);
        for (int i = 0; i < 31; ++i) {
            int p = (i + t) % 31;
            A[p] = G[i];
        }
        (void)send_packet(A); // Cleopatra taints, but we ignore here
    }

    // Reliable indices in ascending order
    vector<int> reliable;
    for (int i = 0; i < 31; ++i) if (G[i]) reliable.push_back(i);

    // Payload: 10-bit header + message bits
    vector<bool> payload = encode_len10((int)M.size());
    payload.insert(payload.end(), M.begin(), M.end());

    // === Phase 2: Send payload, 16 bits per packet ===
    size_t pos = 0;
    while (pos < payload.size()) {
        vector<bool> A(31, false);
        for (int j = 0; j < (int)reliable.size(); ++j) {
            if (pos < payload.size()) {
                A[reliable[j]] = payload[pos++];
            }
        }
        (void)send_packet(A);
    }
}

// ================= RECEIVER SIDE =================

// Helper: strict majority from 31 packets
static bool majority31(const array<int,31>& ones, int i) {
    return ones[i] > 15; // must be >=16 to win
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int P = (int)R.size();

    // === Phase 1: reconstruct G ===
    array<int,31> ones{}; ones.fill(0);
    for (int t = 0; t < 31; ++t) {
        for (int i = 0; i < 31; ++i) {
            int phys = (i + t) % 31;
            if (R[t][phys]) ++ones[i];
        }
    }
    vector<bool> G(31, false);
    for (int i = 0; i < 31; ++i) {
        G[i] = (ones[i] > 15);
    }

    // Reliable indices in ascending order
    vector<int> reliable;
    for (int i = 0; i < 31; ++i) if (G[i]) reliable.push_back(i);

    // === Phase 2: parse payload ===
    vector<bool> bitstream;
    for (int t = 31; t < P; ++t) {
        for (int idx : reliable) {
            bitstream.push_back(R[t][idx]);
        }
    }

    if (bitstream.size() < 10) return {}; // defensive guard

    // First 10 bits = length
    int S = 0;
    for (int i = 0; i < 10; ++i) {
        S = (S << 1) | (bitstream[i] ? 1 : 0);
    }

    // Next S bits = message
    vector<bool> M;
    M.reserve(S);
    for (int i = 10; i < 10 + S && i < (int)bitstream.size(); ++i) {
        M.push_back(bitstream[i]);
    }
    return M;
}

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