Submission #1209307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209307		andrej246	Message (IOI24_message)	C++20	90.25 / 100	433 ms	860 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;

ll packets = 68;
ll msize = 41;
ll checksize = 23;
vector<vb> check = {{0,1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1},{1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,1,0,0,1},{1,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,1,1,1},{1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0},{0,1,0,1,1,1,0,1,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0},{0,0,1,0,0,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,1,0},{0,0,1,0,0,0,0,1,1,1,0,0,0,1,1,0,1,1,0,1,1,0,0},{1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1},{0,0,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,1,0,0,1,1},{1,0,1,0,0,1,1,1,1,1,1,0,1,0,1,1,0,0,0,0,1,1,1},{1,1,1,1,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,0,1,0,1},{0,0,1,1,0,1,1,1,0,1,0,0,0,1,0,1,0,0,0,0,1,1,0},{1,0,1,0,0,0,0,1,0,1,0,1,1,1,0,0,1,0,1,0,1,1,0},{1,0,1,0,1,0,1,1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1},{1,1,1,1,0,0,1,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1},{0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,1,0,1},{0,1,0,0,0,0,0,1,1,1,1,0,1,0,0,1,0,0,0,0,1,1,1},{0,1,1,0,1,1,1,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,0},{1,0,1,0,1,1,1,1,0,1,1,1,0,0,1,1,0,1,1,1,0,1,0},{1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0},{0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,0,1,0,0,0,0,1,1},{1,1,0,0,0,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0},{1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,1,0,1,1,0},{0,0,0,1,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,1,0,0,0},{0,0,1,1,1,1,1,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1},{1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,0,1,0,1,0,1,1},{0,0,1,0,0,1,0,0,1,0,0,1,1,0,1,1,1,1,0,1,1,0,1},{1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,1,0,0,0},{1,0,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,1,1,1},{1,0,1,0,0,0,0,1,1,1,1,0,1,0,0,1,0,0,0,0,1,1,0}};

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));

    ll t = 0;
    vb ch = check[x];
    while ((!m.empty()) || (!meta.empty()) || (t < packets)) {
        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 (b == x && t >= packets-checksize) {
                p[x] = ch.back();
                ch.pop_back();
                continue;
            }
            if (c[b]) continue;
            if (m.empty()) continue;
            p[b] = m.back();
            m.pop_back();
        }
        send_packet(p);
        t++;
    }
}

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

    ll x = -1;
    FOR(i,31) {
        // FOR(j,68) cout << r[j][i] << " ";
        // cout << endl;
        bool ok = true;
        FOR(y,checksize) {
            if (r[y][i] != check[i][y]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            // assert(x == -1);
            x = i;
        }
    }
    // assert(x != -1);
    

    ll 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 (b == x && t >= packets-checksize) continue;
            if (c[b]) continue;
            if ((ll)message.size() < n) {
                message.push_back(p[b]);
            }
        }
        t++;
    }

    return message;
}

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