Submission #1256976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256976		nerrrmin	Message (IOI24_message)	C++20	43.96 / 100	445 ms	864 KiB

message

#include "message.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
bool known[40];
void send_message(std::vector<bool> M, std::vector<bool> C)
{
    for (int i = 0; i < C.size(); ++ i)
        C[i] = 1- C[i];
    for (int i = 0; i < 31; ++ i)
        known[i] = 0;
    vector < bool > ones, zeroes;
    for (int i = 0; i < 31; ++ i)
        ones.pb(1);
    for (int i = 0; i < 31; ++ i)
        zeroes.pb(0);
    int some = 0, j = -1;
    for (int i = 0; i < 31; ++ i)
    {
        if(some == 0)
        {
            if(C[i] == 0)send_packet(zeroes);
            else
            {
                send_packet(ones);
                known[i] = 1;
                some = 1;
            }
            j = i;
        }
        else
        {
            vector < bool > ans;
            int to_be_discovered = j+1;
            if(to_be_discovered >= 31)break;
            vector < int > newfound;
            for (int pos = 0; pos < 31; ++ pos)
            {
                if(!known[pos])ans.pb(0);
                else
                {
                    if(to_be_discovered < 31)
                    {
                        ans.pb(C[to_be_discovered]);
                        if(C[to_be_discovered] == 1)newfound.pb(to_be_discovered);
                    }
                    else ans.pb(0);
                    to_be_discovered ++;
                    j ++;
                }

            }
            for (auto x: newfound)
                known[x] = 1;
            send_packet(ans);
        }
    }
    vector < int > ours;
    for (int i = 0; i < 31; ++ i)
        if(known[i])ours.pb(i);


    int sz = M.size();
    int step = 0;
    vector < bool > szpacket;
    for (int i = 0; i < 31; ++ i)
    {
        if(known[i] == 1)
        {

            if(sz &  (1 << step))szpacket.pb(1);
            else szpacket.pb(0);
            step ++;
        }
        else szpacket.pb(0);
    }
    send_packet(szpacket);


    int i = 0;
    int s = M.size();
    while(i < s)
    {
        vector < bool > packet;
        for (int j = 0; j < 31; ++ j)
            packet.pb(0);
        for (auto x: ours)
        {
            if(i >= s)break;
            packet[x] = M[i];
            i ++;
        }
        send_packet(packet);
    }
}
int val[40];
std::vector<bool> receive_message(std::vector<std::vector<bool>> R)
{

    int found = 0, pos = 0;
    for (int i = 0; i < 31; ++ i)
        val[i] = -1;
    int curr = 0;

    while(pos < 31)
    {
        if(!found)
        {

            int cnt0 = 0, cnt1 = 0;
            for (auto x: R[curr])
            {
                if(x)cnt1 ++;
                else cnt0 ++;
            }
            if(cnt0 >= cnt1)val[pos] = 0;
            else val[pos] = 1;
            if(val[pos] == 1)found = 1;
            pos ++;
        }
        else
        {
            vector < pair < int, int > > mp;
            for (int i = 0; i < 31; ++ i)
            {
                if(val[i] == 1)
                {
                    int x = R[curr][i];
                    mp.pb(make_pair(pos, x));
                    pos ++;
                }
            }
            for (auto &[pp, vv]: mp)
            {
                val[pp] = vv;
            }
        }
        curr ++;
    }

    int sz = 0, id = 0, step = 1;

    for (auto x: R[curr])
    {
        if(val[id] == 1)
        {
            if(x)sz += step;
            step *= 2;
        }

        id ++;
    }
    curr ++;
    int s = sz;

    vector < bool > ans;
    int mark = 0;
    while(curr < R.size())
    {
        for (int i = 0; i < 31; ++ i)
        {
            if(val[i] == 1)
                ans.pb(R[curr][i]);
        }
        curr ++;
    }
    while(ans.size() > s)
        ans.pop_back();
    return ans;
}

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