Submission #1231540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231540		bangan	Message (IOI24_message)	C++20	61.19 / 100	445 ms	872 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) {
    auto work1 = [&]() -> vector<vector<bool>> {
        int bad=0;
        vector<int> ok;
        vector<vector<bool>> ret;
        for (int i=0; i<N && ok.size() != 16 && bad != 15;) {
            if (ok.empty()) {
                ret.pb(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++;
                }
                ret.pb(pac);
            
                for (int k=i; k < i+j; k++) {
                    if (!C[k]) ok.pb(k);
                    else bad++;
                }
                i+=j;
            }
        }
        return ret;
    };
    auto work2 = [&]() -> vector<vector<bool>> {
        int bad=0;
        vector<int> ok;
        vector<vector<bool>> ret;
        for (int i = N-1; 0<=i && ok.size() != 16 && bad != 15;) {
            if (ok.empty()) {
                ret.pb(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() && 0 <= i-j) {
                    pac[ok[j]] = C[i-j];
                    j++;
                }
                ret.pb(pac);
            
                for (int k=i; i-j < k; k--) {
                    if (!C[k]) ok.pb(k);
                    else bad++;
                }
                i-=j;
            }
        }
        return ret;
    };

    auto x = work1();
    auto y = work2();

    if (x.size() < y.size()) {
        send_packet(vector<bool>(N, false));
        for (auto vec : x) send_packet(vec);
    }
    else {
        send_packet(vector<bool>(N, true));
        for (auto vec : y) send_packet(vec);
    }



    vector<int> ok;
    for (int i=0; i<N; i++) if (!C[i]) ok.pb(i);

    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());
    bool st;
    {
        int cnt[2] {};
        auto vec = R.back();
        R.pop_back();
        for (bool x : vec) cnt[x]++;
        if (cnt[0]>cnt[1]) st=0;
        else st=1;
    }

    vector<bool> C(N);

    if (st==0) {
        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;
            }
        }
        for (int j=i; j<N; j++) {
            if (ok.size()==16) C[j] = true;
            else if (bad==15) C[j] = false;
            else assert(false);
        }
    }
    else {
        vector<int> ok;
        int bad = 0;

        int i;
        for (i = N-1; 0<=i && 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() && 0 <= i-j) {
                    C[i-j] = vec[ok[j]];
                    j++;
                }

                for (int k=i; i-j < k; k--) {
                    if (!C[k]) ok.pb(k);
                    else bad++;
                }
                i-=j;
            }
        }
        for (int j=i; 0<=j; j--) {
            if (ok.size()==16) C[j] = true;
            else if (bad==15) C[j] = false;
            else assert(false);
        }
    }
    reverse(R.begin(), R.end());

    int i;
    vector<int> ok;
    for (i=0; i<N; i++) if (!C[i]) ok.pb(i);

    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: 10 / 10
• Subtask 2: 51.192 / 90