Submission #1194015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194015		Nelt	Message (IOI24_message)	C++20	0 / 100	73 ms	840 KiB

message

#include "message.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
ll cost(vector<bool> &c)
{
    ll tot = 0;
    ll ptr = 0, sz = 0;
    while (ptr < 31 and sz < 16)
    {
        ll bal = 31 - ptr - (16 - sz);
        bool inc = 0;
        if (bal < (16 - sz))
        {
            if (c[ptr] == 0)
                inc = 1;
            ptr++;
        }
        tot++;
        ll tmp = sz;
        for (ll i = 0; i < tmp and ptr < 31; i++, ptr++)
            sz += c[ptr] == 0;
        sz += inc;
    }
    return tot;
}
void send_message(vector<bool> a, vector<bool> c)
{
    vector<bool> msg(31, 0), revc = c;
    reverse(revc.begin(), revc.end());
    bool flg = cost(revc) < cost(c);
    send_packet(vector<bool>(31, cost(revc) < cost(c)));
    if (flg)
        swap(revc, c);
    vector<ll> fixed;
    ll ptr = 0;
    while (ptr < 31 and fixed.size() < 16)
    {
        ll bal = 31 - ptr - (16 - fixed.size());
        ll good = -1;
        if (bal < 16 - fixed.size())
        {
            msg = vector<bool>(31, c[ptr]);
            if (c[ptr] == 0)
                good = flg ? 30 - ptr : ptr;
            ptr++;
        }
        ll sz = fixed.size();
        for (ll i = 0; i < sz and ptr < 31; i++, ptr++)
        {
            msg[fixed[i]] = c[ptr];
            if (c[ptr] == 0)
                fixed.push_back(flg ? 30 - ptr : ptr);
        }
        if (good != -1) fixed.push_back(good);
        send_packet(msg);
    }
    if (fixed.size() != 16)
        exit(0);
    for (ll i = 0; i < 16; i++)
        msg[fixed[i]] = (a.size() >> i & 1);
    send_packet(msg);
    for (ll i = 0; i < a.size(); i += 16)
    {
        for (ll j = 0; j + i < a.size() and j < 16; j++)
            msg[fixed[j]] = a[i + j];
        send_packet(msg);
    }
}
bool majority(vector<bool> &c, ll ind)
{
    return count(c.begin() + ind, c.end(), 1) * 2 > (31 - ind);
}
vector<bool> receive_message(vector<vector<bool>> a)
{
    vector<bool> c(31, 1);
    bool flg = majority(a[0], 0);
    ll ptr = 0, cur = 1;
    vector<ll> fixed;
    while (ptr < 31 and fixed.size() < 16)
    {
        ll bal = 31 - ptr - (16 - fixed.size());
        ll good = -1;
        if (bal < 16 - fixed.size())
        {
            if (majority(a[cur], ptr) == 0)
                good = flg ? 30 - ptr : ptr;
            ptr++;
        }
        ll sz = fixed.size();
        for (ll i = 0; i < sz and ptr < 31; i++, ptr++)
        {
            c[ptr] = a[cur][fixed[i]];
            if (c[ptr] == 0)
                fixed.push_back(flg ? 30 - ptr : ptr);
        }
        if (good != -1) fixed.push_back(good);
        cur++;
    }
    ll sz = 0;
    for (ll i = 0; i < 16; i++)
        if (a[cur][fixed[i]])
            sz += 1 << i;
    vector<bool> ans(sz);
    for (ll i = 0; i < sz; i++)
        ans[i] = a[cur + 1 + (i >> 4)][fixed[i & 15]];
    return ans;
}

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