Submission #1211951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211951		vanea	Message (IOI24_message)	C++20	30.33 / 100	527 ms	856 KiB

message

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

void send_message(vector<bool> M, vector<bool> C) {
    int s = M.size();
    vector<bool> a, b;
    for(int i = 0; i < 31; i++) {
        a.push_back(1);
        b.push_back(0);
    }
    int idx = -1, idx1;
    for(int i = 0; i < 31; i++) {
        if(C[i]) continue;
        if(idx == -1) idx = i;
        else {
            idx1 = i;
            break;
        }
    }
    for(int i = 0; i < 31; i++) {
        if(i > idx1) {
            a[idx1] = (s & (1 << (i - idx1 - 1)));
            b[idx1] = (s & (1 << (i - idx1 - 1)));
        }
        if(C[i]) {
            send_packet(a);
        }
        else {
            send_packet(b);
        }
    }
    idx = 0;
    while(idx < s) {
        vector<bool> now;
        for(int i = 0; i < 31; i++) {
            if(C[i]) now.push_back(0);
            else now.push_back(M[idx++]);
            if(idx > s) break;
        }
        while(now.size() < 31) now.push_back(0);
        send_packet(now);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) {
    int s = 0;
    vector<bool> ans;
    int idx = -1;
    int idx1 = -1;
    for(int i = 0; i < 31; i++) ans.push_back(1);
    for(int i = 0; i < 31; i++) {
        int cnt = 0;
        for(auto it : R[i]) {
            cnt += it;
        }
        if(idx != -1) {
            if(R[i][idx] == 1) ans[i] = false;
            if(idx1 != -1) {
                s |= (R[i][idx1] << (i-idx1-1));
            }
            else {
                if(ans[i]) idx1 = i;
            }
        }
        else if(cnt >= 16) {
            ans[i] = false;
        }
        else idx = i;
    }
    vector<bool> res;
    for(int i = 31; i < R.size(); i++) {
        for(int j = 0; j < 31; j++) {
            if(res.size() < s && ans[j]) {
                res.push_back(R[i][j]);
            }
        }
    }
    return res;
}

/*int main()
{
    send_message({0, 1, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1});
    vector<bool> ans = receive_message(R);
    for(auto it : ans) {
        cout << it << ' ';
    }
    return 0;
}*/

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