Submission #1216256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216256		shmax	Message (IOI24_message)	C++20	87.16 / 100	393 ms	876 KiB

message

#include <bits/stdc++.h>
#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 < 31; i++) {
        int g = next[i];
        int diff = next[i] - i;
        if (diff < 0) diff += 31;
        next[i] = diff;
    }
    for (int i = 0; i < 4; 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 < 4; j++) {
            next[i] |= (R[j][i] << j);
        }
        if (next[i] == 0) next[i] = 16;
        next[i] += i;
        next[i] %= 31;
    }
    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;
    }
    sort(good.begin(), good.end());
    int sz = 0;
    for (int i = 0; i < 16; i++) {
        sz |= (R[4][good[i]] << i);
    }
    vec<bool> M;
    for (int i = 5; 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: 77.1637 / 90