Submission #1242606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242606		fskarica	Message (IOI24_message)	C++20	30.33 / 100	562 ms	856 KiB

message

#include <bits/stdc++.h>
//#include "message.h"

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

//vector <vector<bool>> bla;
//std::vector<bool> send_packet(std::vector<bool> A) {
//    bla.push_back(A);
//    return A;
//}

std::vector<bool> send_packet(std::vector<bool> A);

void send_message(std::vector<bool> M, std::vector<bool> C) {
    vector <bool> zero, one;

    for (int i = 0; i < 31; i++) {
        zero.push_back(0);
        one.push_back(1);
    }

    for (int i = 0; i < 30; i++) {
        if (C[i] == 0) send_packet(zero);
        else send_packet(one);
    }

    int n = M.size();
    vector <bool> sz(31, 0);
    for (int i = 30; i >= 0; i--) {
        if (C[i]) continue;

        if (n % 2) sz[i] = 1;
        n /= 2;
    }
    send_packet(sz); /// this sends how long is M

    int pos = 0;
    vector <bool> msg(31, 0);
    for (auto e : M) {
        while (pos < 31 && C[pos]) pos++;
        if (pos == 31) {
            pos = 0;
            send_packet(msg);
            for (int i = 0; i < 31; i++) msg[i] = 0;
        }
        while (pos < 31 && C[pos]) pos++;

        if (e) msg[pos] = 1;
        pos++;
    }

    if (pos != 0) send_packet(msg);
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> R) {
    vector <int> C(31, 0);

//    cout << R.size() << " rsize()\n";

    int cnt0 = 0, cnt1 = 0;
    for (auto e : R) {
        if (cnt0 + cnt1 == 30) break;

        int cntOne = 0, cntZero = 0;
        for (auto e2 : e) {
            if (e2 == 0) cntZero++;
            else cntOne++;
        }

        if (cntOne < cntZero) cnt0++;
        else cnt1++, C[cnt0 + cnt1 - 1] = 1;
    }
    if (cnt1 < 15) C[30] = 1;

//    cout << "C - "; for (int i = 0; i < 31; i++) cout << C[i] << " "; cout << "\n";

    int sz = 0;
    int cnt = 0;
    for (int i = 30; i >= 0; i--) {
        if (C[i]) continue;
        sz += R[30][i] * (1 << cnt);
        cnt++;
    }

//    cout << "sz - " << sz << "\n";

    vector <bool> ret;
    cnt = 0;
    for (int i = 31; i < R.size(); i++) {
        for (int j = 0; j < 31; j++) {
            if (cnt == sz) continue;
            if (C[j]) continue;

            int x = R[i][j];
            ret.push_back(x);
            cnt++;
        }
    }

    return ret;
}

//int main() {
//    send_message({0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0}, {0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1});
////    cout << bla.size() << " bla size\n\n";
//
//    vector <bool> sol = receive_message(bla);
//    cout << "sol - "; for (auto e : sol) cout << e << " "; cout << "\n";
//}

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