Submission #1297871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297871		gesp3011v2	Message (IOI24_message)	C++20	43.96 / 100	434 ms	832 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back

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<<=1;
        }
        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