Submission #1236154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236154		bangan	Message (IOI24_message)	C++20	0 / 100	343 ms	848 KiB

message

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

#define pb push_back

// const int N = 31;

void send_message(std::vector<bool> M, std::vector<bool> C) {
    int N = 31;
    M.pb(1);
    vector<int> d(N);
    for (int i=0; i<N; i++) if (!C[i]) {
        for (int j=1; j<N; j++) if (!C[(i+j) % N]) {
            d[i] = j;
            break;
        }
    }
    vector<vector<bool>> col(N);
    for (int i=0; i<N; i++) if (!C[i]) {
        int x = d[i];
        assert(0<x);
        while (0<x) {
            col[i].pb(x%2);
            col[i].pb(0);
            x/=2;
        }
        col[i].pop_back();
        col[i].pb(1);
    }
    int p=0, q=0;
    for (int x : M) {
        while (C[q] || p+1 <= col[q].size()) {
            q++;
            if (q==N) q=0, p++;
        }
        col[q].pb(x);
        assert(col[q].size()==p+1);
    }
    assert(p<66);
    for (int i=0; i<N; i++) if (col[i].size()<66) col[i].pb(0);
    for (int i=0; i<66; i++) {
        vector<bool> pac;
        for (int j=0; j<N; j++) pac.pb(col[j][i]);
        send_packet(pac);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    int N = 31;
    vector col(N, vector<bool>(66));
    for (int i=0; i<N; i++) for (int j=0; j<66; j++) col[i][j] = R[j][i];
    for (int i=0; i<N; i++) reverse(col[i].begin(), col[i].end());
    vector<int> d(N);
    for (int i=0; i<N; i++) {
        for (int p=0; p<30; p++) {
            int r = col[i].back();
            col[i].pop_back();
            bool flg = col[i].back();
            col[i].pop_back();
            d[i] += r * (1 << p);
            if (flg) break;
        }
    }
    auto test = [&](int i) -> vector<bool> {
        vector<bool> ret(N, 1);
        while (ret[i]) {
            ret[i] = 0;
            if (!d[i]) return {};
            i = (i + d[i]) % N;
        }
        if (count(ret.begin(), ret.end(), 0)==16) return ret;
        else return {};
    };
    vector<bool> C;
    for (int i=0; C.empty(); i++) {
        vector<bool> res = test(i);
        if (!res.empty()) C = res;
    }
    assert(count(C.begin(), C.end(), 0)==16);
    vector<bool> M;
    int p=65, q=0;
    while (0<=p) {
        while (C[q] || col[q].size() < p+1) {
            q++;
            if (q==N) q=0, p--;
        }
        if (0<=p) {
            assert(col[q].size()==p+1);
            M.pb(col[q].back());
            col[q].pop_back();
        }
    }
    while (!M.back()) M.pop_back();
    M.pop_back();
    return M;
}

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