Submission #1245942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245942		thinknoexit	Message (IOI24_message)	C++20	100 / 100	413 ms	868 KiB

message

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

void send_message(vector<bool> M, vector<bool> C) {
    vector<bool> m;
    while (m.size() + M.size() < 1024) {
        m.push_back(0);
    }
    m.push_back(1);
    for (bool x : M) m.push_back(x);
    vector<int> pos;
    for (int i = 0;i < 31;i++) {
        if (!C[i]) pos.push_back(i);
    }
    vector<vector<bool>> p(66, vector<bool>(31, 0)), used(66, vector<bool>(31, 0));
    for (int i = 0;i < 16;i++) {
        int nxt = (pos[(i + 1) % 16] - pos[i] + 31) % 31;
        for (int j = 0;j < nxt;j++) {
            p[j][pos[i]] = (j == nxt - 1);
            used[j][pos[i]] = 1;
        }
    }
    int tot = 0;
    for (int i = 0;i < 66;i++) {
        for (int j = 0;j < 31;j++) {
            if (C[j] || used[i][j]) continue;
            p[i][j] = m[tot++];
        }
    }
    for (int i = 0;i < 66;i++) send_packet(p[i]);
}
int nxt[33], deg[33];
vector<bool> receive_message(vector<vector<bool>> R) {
    memset(deg, 0, sizeof deg);
    for (int j = 0;j < 31;j++) {
        int now = 0;
        while (now < 66 && !R[now][j]) now++;
        if (now < 66) {
            nxt[j] = (j + now + 1) % 31, deg[(j + now + 1) % 31]++;
            // cerr << j << "->" << nxt[j] << '\n';
        }
        else nxt[j] = -1;
    }
    queue<int> q;
    for (int j = 0;j < 31;j++) {
        if (deg[j] == 0) q.push(j);
    }
    vector<vector<bool>> used(66, vector<bool>(31, 0));
    vector<bool> C(31, 1), cycle(31, 1);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cycle[v] = false;
        if (nxt[v] != -1 && --deg[nxt[v]] == 0) q.push(nxt[v]);
    }
    for (int i = 0;i < 31;i++) {
        if (!cycle[i]) continue;
        cycle[i] = 0;
        int sz = 1;
        int now = nxt[i];
        vector<int> nds;
        nds.push_back(i);
        while (now != i) {
            nds.push_back(now);
            cycle[now] = 0;
            sz++;
            now = nxt[now];
        }
        if (sz != 16) continue;
        for (auto& x : nds) {
            C[x] = false;
            // cerr << "Found :" << x << '\n';
        }
        break;
    }
    for (int j = 0;j < 31;j++) {
        if (C[j]) continue;
        int now = 0;
        used[now][j] = 1;
        while (!R[now][j]) {
            used[++now][j] = 1;
        }
    }
    vector<bool> res;
    bool ch = 0;
    for (int i = 0;i < 66;i++) {
        for (int j = 0;j < 31;j++) {
            if (C[j] || used[i][j]) continue;
            if (ch) res.push_back(R[i][j]);
            ch |= R[i][j];
        }
    }
    return res;
}

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