Submission #1209298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209298		andrej246	Message (IOI24_message)	C++20	76.16 / 100	460 ms	852 KiB

message

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

#define NL '\n'
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a:v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a:v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;



void send_message(std::vector<bool> m, std::vector<bool> c) {
    reverse(all(m));

    ll x = 0;
    FOR(i,31) {
        if (!c[i] && !c[(i+1)%31]) {
            x = i;
        }
    }

    ll x2 = x;
    FOR(b,5) {  
        vb p(31,x2%2);
        send_packet(p);
        x2 /= 2;
    }
    
    vl meta;

    reverse(all(c));
    for (auto x: c) meta.push_back(x);
    ll n = m.size()-1;
    FOR(b,10) {  
        meta.push_back(n%2);
        n /= 2;
    }
    reverse(all(c));

    while (!m.empty() || !meta.empty()) {
        vb p(31);
        bool freemeta = false;
        if (meta.empty()) freemeta = true;
        else {
            p[x] = meta.back();
            meta.pop_back();
        }
        FOR(b,31) {
            if (b == x && !freemeta) continue;
            if (c[b]) continue;
            if (m.empty()) break;
            p[b] = m.back();
            m.pop_back();
        }
        send_packet(p);
    }
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> r) {
    reverse(all(r));

    ll pw = 1;
    ll x = 0;
    FOR(b,5) {
        vb p = r.back();
        r.pop_back();
        ll s = 0;
        FOR(i,31) s += p[i];
        if (s > 15) x += pw;
        pw *= 2;
    }

    pw = 512;
    ll n = 1;
    set<ll> goodbits;
    ll ind = 0;
    ll freemeta = -1;
    ll t = 0;
    vl c(31);
    FORR(i,(ll)r.size()) {
        vb p = r[i];
        if (pw != 0) {
            ll b = p[x];
            n += pw*b;
            if (pw > 1) pw /= 2;
            else pw = 0;
        } else if (ind < 31) {
            ll b = p[x];
            c[ind] = b;
            if (!b && ind != x) goodbits.insert(ind);
            ind++;
        } else {
            freemeta = t;
            break;
        }
        t++;
    }
    if (freemeta == -1) freemeta = t;

    vb message;

    t = 0;
    while ((ll)message.size() < n) {
        vb p = r.back();
        r.pop_back();
        if (freemeta == t) {
            goodbits.insert(x);
        }
        // for (auto b: goodbits) {
        FOR(b,31) {
            if (b == x && t < freemeta) continue;
            if (c[b]) continue;
            if ((ll)message.size() < n) {
                message.push_back(p[b]);
            }
        }
        t++;
    }

    return message;
}

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