Submission #1216277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216277		shmax	Message (IOI24_message)	C++20	100 / 100	412 ms	860 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) {

    reverse(M.begin(), M.end());
    M.push_back(true);
    while (M.size() < 1025) M.push_back(false);
    reverse(M.begin(), M.end());
    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 diff = next[i] - i;
        if (diff < 0) diff += 31;
        next[i] = diff;
    }
    vec<int> good;
    for (int i = 0; i < 31; i++) {
        if (C[i] == 0)
            good.push_back(i);
    }

    vec<vec<bool>> R(66, vec<bool>(31, false));
    int ptr = 0;
    for (int i: good) {
        for (int j = 0; j < next[i] - 1; j++)
            R[j][i] = false;
        R[next[i] - 1][i] = true;
        for (int j = next[i]; j < 66; j++) {
            R[j][i] = M[ptr++];
        }
    }
    for (const auto &row: R)
        send_packet(row);


//    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<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);
    vec<int> st(31, 0);
    for (int i = 0; i < 31; i++) {
        int cnt = 0;
        while (!R[cnt][i] and cnt < 31) cnt++;
        cnt++;
        st[i] = cnt;
        next[i] = i + cnt;
        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());
    vec<bool> M;
    for (int i: good) {
        for (int j = st[i]; j < 66; j++)
            M.push_back(R[j][i]);
    }
    reverse(M.begin(), M.end());
    while (!M.back()) M.pop_back();
    M.pop_back();
    reverse(M.begin(), M.end());
    return M;
}

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