Submission #1231319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231319		sahasrad	Message (IOI24_message)	C++20	42.26 / 100	526 ms	864 KiB

message

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

// vector<vector<bool>> packet_queue;
// vector<bool> send_packet(vector<bool> A) {
//     packet_queue.push_back(A);
//     return A;
// }


int mask = 65535;
vector<int> seq = {25226, 3520, 25771, 26888, 22115, 61712, 45676, 17833, 47399, 59849, 13569, 14556, 506, 21088, 18877, 48567, 23510, 48339, 3865, 22440, 16930, 35168, 49562, 60198, 50417, 19792, 14099, 16964, 37461, 32187, 51383, 57031};
int check = 22;

void encode_and_send(vector<bool> &M, vector<bool> &C) {
    vector<bool> packet(31);

    int ptr = 0;
    for (int j = 0; j < 31; j++) {
        if (C[j]) continue;
        packet[j] = M[ptr++];
    }

    send_packet(packet);
}

void send_message(vector<bool> M, vector<bool> C) {
    bool invert = false;
    if (!M.back()) {
        for (int i = 0; i < M.size(); i++) {
            M[i] = !M[i];
        }
        invert = true;
    }

    for (int i = 0; i < check; i++) {
        int val = seq[i] ^ (invert ? mask : 0);
        vector<bool> bits(16);
        for (int j = 0; j < 16; j++) {
            bits[j] = val & 1;
            val >>= 1;
        }
        encode_and_send(bits, C);
    }

    int packets = (M.size() + 15) / 16;
    for (int i = 0; i < packets; i++) {
        vector<bool> m(16);
        for (int j = 0; j < 16; j++) {
            int idx = i * 16 + j;
            if (idx >= M.size()) break;
            m[j] = M[idx];
        }
        encode_and_send(m, C);
    }
}

vector<int> get_subseq(vector<vector<bool>> R, bool invert) {
    vector<int> bits;
    int tokenPtr = 0;
    int ptr = 0;
    while (tokenPtr < 16 && ptr < 31) {
        bool works = true;
        for (int i = 0; i < check; i++) {
            if (R[i][ptr] != (((seq[i] & (1 << tokenPtr)) > 0) ^ invert)) {
                works = false;
                break;
            }
        }

        if (works) {
            tokenPtr++;
            bits.push_back(ptr);
        }
        ptr++;
    }
    return bits;
}

vector<bool> receive_message(vector<vector<bool>> R) {
    vector<int> bits = get_subseq(R, false);
    bool invert = false;
    if (bits.size() < 16) {
        invert = true;
        bits = get_subseq(R, true);
    }


    vector<bool> ans;
    for (int i = check; i < R.size(); i++) {
        for (int j = 0; j < 16; j++) {
            ans.push_back(R[i][bits[j]]);
        }
    }

    while (ans.back() == 0) {
        ans.pop_back();
    }

    if (invert) {
        for (int i = 0; i < ans.size(); i++) {
            ans[i] = !ans[i];
        }
    }

    return ans;
}

// int main() {
// /*
//     send_message([0, 1, 1, 0],
//     [, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ]
//     );
//
//     */
//
//     vector<bool> C = {1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0};
//     send_message({1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, C);
//
//     for (vector<bool> &packet : packet_queue) {
//         for (int i = 0; i < 31; i++) {
//             if (C[i]) packet[i] = rand() % 2;
//         }
//     }
//     vector<bool> ans = receive_message(packet_queue);
//
//     cout << "Received message: ";
//     for (bool bit : ans) {
//         cout << bit;
//     }
//
//     return 0;
// }

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