Submission #1216235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216235		shmax	Message (IOI24_message)	C++20	10 / 100	352 ms	820 KiB

message

#include <set>
#include "message.h"

using namespace std;

template<typename T>
using vec = vector<T>;

void send_message(std::vector<bool> M, std::vector<bool> C) {
    vec<int> next(31, 0);
    int last = -1;
    for (int i = 0; i < 31; i++) {
        if (C[i] == 0) {
            last = i;
            break;
        }
    }
    for (int i = 30; i >= 0; i--) {
        if (C[i] == 0) {
            next[i] = last;
            last = i;
        }
    }
    for (int i = 0; i < 5; i++) {
        vec<bool> d(31, false);
        for (int j = 0; j < 31; j++) {
            d[j] = (next[j] >> i) & 1;
        }
        send_packet(d);
    }
    vec<int> good;
    for (int i = 0; i < 31; i++) {
        if (C[i] == 0)
            good.push_back(i);
    }
    vec<bool> d(31, false);
    for (int j = 0; j < 16; j++) {
        d[good[j]] = (M.size() >> j) & 1;
    }
    send_packet(d);
    while (M.size() % 16 != 0) {
        M.push_back(false);
    }
    for (int i = 0; i < M.size(); i += 16) {
        for (int j = 0; j < 16; j++) {
            d[good[j]] = M[i + j];
        }
        send_packet(d);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    vec<int> next(31, 0);
    for (int i = 0; i < 31; i++) {
        for (int j = 0; j < 5; j++) {
            next[i] |= (R[j][i] << j);
        }
    }
    vec<int> good;
    for (int start = 0; start < 31; start++) {
        vec<int> cur;
        int pos = start;
        cur.push_back(pos);
        pos = next[pos];
        if (pos > 31) continue;
        set<int> seen;
        while (pos != start) {
            if (pos > 31) break;
            if (seen.count(pos)) break;
            seen.insert(pos);
            cur.push_back(pos);
            pos = next[pos];
        }
        if (pos != start) continue;
        if (cur.size() != 16) continue;
        good = cur;
        break;
    }
    int sz = 0;
    for (int i = 0; i < 16; i++) {
        sz |= (R[5][good[i]] << i);
    }
    vec<bool> M;
    for (int i = 6; i < R.size(); i++) {
        for (int j = 0; j < 16; j++) {
            M.push_back(R[i][good[j]]);
        }
    }
    while (M.size() > sz) {
        M.pop_back();
    }
    return M;
}

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