Submission #1234393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234393		bangan	Message (IOI24_message)	C++20	83.31 / 100	427 ms	864 KiB

message

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

#define pb push_back


void send_message(std::vector<bool> M, std::vector<bool> C) {
    int N = 31;
    M.pb(1);

    int f;
    for (int i = N-1; 0<=i; i--) if (!C[i]) f=i;
    assert(f<16);
    for (int i=0; i<4; i++) send_packet(vector<bool>(N, f>>i&1));

    vector<vector<bool>> send;
    for (int i=0; i<N; i++) {
        if (i==f) continue;
        vector<bool> vec(N);
        vec[f] = C[i];
        send.pb(vec);
    }

    int p = 0, q = 0;
    for (int i=0; i < M.size(); i++) {
        while (C[q] || (p<N-1 && q==f)) {
            q++;
            if (q==N) p++, q=0;
        }
        if (p==send.size()) send.pb(vector<bool>(N));
        send[p][q] = M[i];
        q++;
        if (q==N) p++, q=0;
    }

    for (auto vec : send) send_packet(vec);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    int N = 31;
    auto MAJ = [&](vector<bool> vec) {
        int cnt[2] {};
        for (auto it : vec) cnt[it]++;
        if (cnt[0]<cnt[1]) return 1;
        else return 0;
    };

    int f=0;
    for (int i=0; i<4; i++) f += MAJ(R[i]) << i;
    R.erase(R.begin(), R.begin() + 4);

    vector<bool> C(N);
    for (int i=0, j=0; i<N; i++) {
        if (i==f) continue;
        C[i] = R[j++][f];
    };

    vector<bool> M;
    for (int i=0; i<R.size(); i++) {
        for (int j=0; j<N; j++) {
            if (C[j] || (i<N-1 && j==f)) continue;
            M.pb(R[i][j]);
        }
    }

    while (!M.back()) M.pop_back();
    M.pop_back();
    return M;
}

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