Submission #1302068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302068		regulardude6	메시지 (IOI24_message)	C++20	100 / 100	407 ms	816 KiB

message

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

static const int W = 31;
static const int SAFE = 16;
static const int QP = 66;
static const int LEN = 1025;

void send_message(vector<bool> M, vector<bool> C) {
    vector<int> safe;
    for (int i = 0; i < W; i++) if (!C[i]) safe.push_back(i);

    vector<int> x(W, 100);
    for (int k = 0; k < SAFE; k++) {
        int a = safe[k];
        int b = safe[(k + 1) % SAFE];
        int d = (b - a + W) % W;
        if (d == 0) d = W;
        x[a] = d;
    }

    int S = (int)M.size();
    vector<bool> msg;
    msg.reserve(LEN);
    int pref = 1024 - S;
    for (int i = 0; i < pref; i++) msg.push_back(false);
    msg.push_back(true);
    for (bool b : M) msg.push_back(b);

    int ptr = 0;
    for (int t = 1; t <= QP; t++) {
        vector<bool> p(W, false);
        for (int i = 0; i < W; i++) {
            if (C[i]) {
                p[i] = false;
            } else {
                if (t < x[i]) p[i] = false;
                else if (t == x[i]) p[i] = true;
                else p[i] = msg[ptr++];
            }
        }
        send_packet(p);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int Q = (int)R.size();
    vector<int> first1(W, Q + 1);
    for (int i = 0; i < W; i++) {
        for (int t = 1; t <= Q; t++) {
            if (R[t - 1][i]) { first1[i] = t; break; }
        }
    }

    vector<int> to(W);
    for (int i = 0; i < W; i++) {
        int d = first1[i];
        if (d > W) d = W;
        to[i] = (i + d) % W;
    }

    vector<int> vis(W, 0), inst(W, 0), parent(W, -1);
    vector<int> cycle_nodes;
    for (int i = 0; i < W; i++) if (!vis[i]) {
        int v = i;
        while (!vis[v]) {
            vis[v] = 1;
            inst[v] = 1;
            v = to[v];
        }
        int u = i;
        while (inst[u]) {
            inst[u] = 0;
            u = to[u];
        }
    }

    vector<int> mark(W, 0), state(W, 0);
    vector<int> stackv;
    function<void(int)> dfs = [&](int s){
        int v = s;
        while (state[v] == 0) {
            state[v] = 1;
            stackv.push_back(v);
            v = to[v];
        }
        if (state[v] == 1) {
            vector<int> cyc;
            for (int j = (int)stackv.size() - 1; j >= 0; j--) {
                cyc.push_back(stackv[j]);
                if (stackv[j] == v) break;
            }
            reverse(cyc.begin(), cyc.end());
            if ((int)cyc.size() == SAFE) cycle_nodes = cyc;
        }
        while (!stackv.empty()) {
            int u = stackv.back();
            stackv.pop_back();
            state[u] = 2;
            if (u == v) break;
        }
    };

    for (int i = 0; i < W; i++) if (state[i] == 0) dfs(i);

    vector<int> safe = cycle_nodes;
    sort(safe.begin(), safe.end());

    vector<int> x(W, 0);
    for (int i = 0; i < W; i++) x[i] = first1[i];

    vector<bool> bits;
    bits.reserve(LEN);
    for (int t = 1; t <= QP; t++) {
        for (int pos : safe) {
            if (t > x[pos]) bits.push_back(R[t - 1][pos]);
        }
    }

    int k = 0;
    while (k < (int)bits.size() && !bits[k]) k++;
    k++;
    vector<bool> M;
    if (k <= (int)bits.size()) {
        M.assign(bits.begin() + k, bits.end());
    }
    return M;
}

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