Submission #1236186

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

message

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

#define pb push_back

const int N = 31;
const int K = 66;

void send_message(std::vector<bool> M, std::vector<bool> C) {
    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-1;
            break;
        }
    }
    vector<vector<bool>> col(N);
    for (int i=0; i<N; i++) if (!C[i]) {
        int x = d[i];
        while (x--) col[i].pb(0);
        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<K);
    for (int i=0; i<N; i++) while (col[i].size()<K) col[i].pb(0);
    for (int i=0; i<K; 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) {
    vector col(N, vector<bool>(K));
    for (int i=0; i<N; i++) for (int j=0; j<K; 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++) {
        while (!col[i].empty() && !col[i].back()) col[i].pop_back(), d[i]++;
        if (!col[i].empty()) col[i].pop_back();
    }
    auto test = [&](int i) -> vector<bool> {
        vector<bool> ret(N, 1);
        while (ret[i]) {
            ret[i] = 0;
            i = (i + d[i] + 1) % 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.size()==N) C = res;
    }
    // assert(count(C.begin(), C.end(), 0)==16);
    vector<bool> M;
    int p = K-1, 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: 10 / 10
• Subtask 2: 90 / 90