Submission #1226403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226403		LucaIlie	Message (IOI24_message)	C++20	100 / 100	414 ms	844 KiB

message

#include "message.h"
#include <stdio.h>
#include <algorithm>

using namespace std;

const int P = 66;
const int B = 31;
const int O = 16;

void send_message(vector<bool> m, vector<bool> c) {
    vector<int> cs;
    for (int b = 0; b < B; b++) {
        if (!c[b])
            cs.push_back(b);
    }

    vector<vector<int>> packets;
    packets.resize(P);
    for (int p = 0; p < P; p++) { 
        packets[p].resize(B);
        for (int i = 0; i < B; i++)
            packets[p][i] = -1;
    }
    for (int i = 0; i < O; i++) {
        int d = (cs[(i + 1) % O] - cs[i] + B - 1) % B;
        for (int p = 0; p < d; p++)
            packets[p][cs[i]] = 0;
        packets[d][cs[i]] = 1;
    }


    m.push_back(0);
    int ind = 0;
    for (int p = 0; p < P; p++) {
        for (int i = 0; i < B; i++) {
            if (!c[i]) {
                if (packets[p][i] == -1) {
                    if (ind < (int)m.size()) {
                        packets[p][i] = m[ind++];
                        // printf("%d %d\n", ind, m[ind - 1]);
                    }
                    else
                        packets[p][i] = 1;
                }
            } else
                packets[p][i] = 0;
        }
    }

    for (int p = 0; p < P; p++) {
        vector<bool> packet(B);
        for (int i = 0; i < B; i++)
            packet[i] = packets[p][i];
        send_packet(packet);
    }


    // for (int p = 0; p < P; p++) {
    //     for (int i = 0; i < B; i++)
    //         printf("%d", (int)packets[p][i]);
    //     printf("\n");
    // }
}

vector<int> adj[B];
bool vis[B];
int parent[B], depth[B];
vector<int> cs;

void dfs(int u, int p) {
    parent[u] = p;
    vis[u] = true;
    for (int v: adj[u]) {
        if (v == p)
            continue;
        if (vis[v]) {
            if (depth[u] - depth[v] == 15) {
                int w = u;
                while (w != v) {
                    cs.push_back(w);
                    w = parent[w];
                }
                cs.push_back(v);
            }
                
        } else {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

vector<bool> receive_message(vector<vector<bool>> r) {
    for (int i = 0; i < B; i++) {
        adj[i].clear();
        vis[i] = false;
        parent[i] = 0;
        depth[i] = 0;
    }
    cs.clear();

    vector<vector<int>> packets(P);
    for (int p = 0; p < P; p++) {
        packets[p].resize(B);
        for (int i = 0; i < B; i++)
            packets[p][i] = r[p][i];
    }
    vector<int> parent(B);
    // for (int p = 0; p < P; p++) {
    //     for (int i = 0; i < B; i++)
    //         printf("%d", (int)packets[p][i]);
    //     printf("\n");
    // }
    for (int i = 0; i < B; i++) {
        int d = 0;
        while (d < O && packets[d][i] == 0) {
            packets[d][i] = -1;
            d++;
        }
        packets[d][i] = -1;

        int p = (i + d + 1) % B;
        adj[i].push_back(p);
        adj[p].push_back(i);

        // printf("%d %d\n", i, p);
    }

    for (int v = 0; v < B; v++) {
        if (vis[v])
            continue;
        dfs(v, -1);
    }

    sort(cs.begin(), cs.end());
    // for (int i = 0; i < (int)cs.size(); i++)
    //     printf("%d ", cs[i]);
    // printf("\n");

    vector<bool> m;
    for (int p = 0; p < P; p++) {
        for (int i = 0; i < O; i++) {
            if (packets[p][cs[i]] != -1)
                m.push_back(packets[p][cs[i]]);
        }
    }

    while (m.back() != 0)
        m.pop_back();
    m.pop_back();

    return m;
}

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