Submission #1231533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231533		bangan	Message (IOI24_message)	C++20	0 / 100	74 ms	840 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 bad=0;
    vector<int> ok;
    for (int i=0; i<N && ok.size() != 16 && bad != 15;) {
        if (ok.empty()) {
            send_packet(vector<bool>(N, C[i]));
            if (!C[i]) ok.pb(i);
            else bad++;
            i++;
        }
        else {
            vector<bool> pac(N, false);
            int j = 0;
            while (j < ok.size() && i+j < N) {
                pac[ok[j]] = C[i+j];
                j++;
            }
            send_packet(pac);
        
            for (int k=i; k < i+j; k++) {
                if (!C[k]) ok.pb(k);
                else bad++;
            }
            i+=j;
        }
    }

    auto cur = ok.begin();
    vector<bool> pac(31, false);
    for (bool x : M) {
        if (cur==ok.end()) {
            send_packet(pac);
            pac = vector<bool>(31, false);
            cur = ok.begin();
        }
        pac[*cur] = x;
        cur++;
    }

    if (cur == ok.end()) {
        send_packet(pac);
        pac = vector<bool>(31, false);
        cur = ok.begin();
    }
    pac[*cur] = true;
    send_packet(pac);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    reverse(R.begin(), R.end());

    vector<bool> C(N, true);
    vector<int> ok;
    int bad = 0;

    int i;
    for (i=0; i<N && ok.size() != 16 && bad != 15;) {
        auto vec = R.back();
        R.pop_back();

        if (ok.empty()) {
            int cnt[2] {};
            for (bool x : vec) cnt[x]++;
            if (cnt[0]<cnt[1]) C[i]=1, bad++;
            else C[i]=0, ok.pb(i);
            i++;
        }
        else {
            int j = 0;
            while (j < ok.size() && i+j < N) {
                C[i+j] = vec[ok[j]];
                j++;
            }

            for (int k=i; k < i+j; k++) {
                if (!C[k]) ok.pb(k);
                else bad++;
            }
            i+=j;
        }
    }
    reverse(R.begin(), R.end());

    for (int j=i; j<N; j++) {
        if (ok.size()==16) C[j] = true;
        else if (bad==15) C[j] = false;
        else assert(false);
    }

    vector<bool> M;
    for (i=0; i+1 < R.size(); i++) {
        auto vec = R[i];
        for (int j=0; j<N; j++) if (!C[j]) M.pb(vec[j]);
    }

    auto vec = R.back();
    int lst=0;
    for (i=0; i<N; i++) if (!C[i] && vec[i]) lst=i;

    for (i=0; i<lst; i++) if (!C[i]) M.pb(vec[i]);
    return M;
}

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