Submission #1240197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240197		Zbyszek99	Message (IOI24_message)	C++20	100 / 100	406 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int nxt_not[31];
bool was_one[31];
bool odw[31];
bool is_ok[31];

void send_message(vector<bool> M, vector<bool> C) 
{
    int siz_ = siz(M)-1;
    vector<bool> M2;
    rep(i,1025-siz(M)-1)
    {
        M2.pb(0);
    }
    M2.pb(1);
    rep(i,siz(M)) M2.pb(M[i]);
    M = M2;
    int cur_bit = 0;
    int first_not = 0;
    rep(i,31)
    {
        if(!C[i])
        {
            first_not = i;
            break;
        }
    }
    for(int i = 30; i >= 0; i--)
    {
        nxt_not[i] = first_not-i;
        if(first_not < i)
        {
            nxt_not[i] = 31 - (i-first_not);
        }
        if(!C[i])
        {
            first_not = i;
        }
    }
    rep(i,31)
    {
        nxt_not[i]--;
    }
    rep(i,100)
    {
        if(cur_bit >= siz(M) && i >= 40) break;
        vector<bool> packet(31);
        rep(bit,31)
        {
            if(i <= nxt_not[bit])
            {
                packet[bit] = 0;
                if(i == nxt_not[bit])
                {
                    packet[bit] = 1;
                }
            }
            else
            {
                packet[bit] = 0;
                if(!C[bit] && cur_bit != siz(M))
                {
                    packet[bit] = M[cur_bit++];
                }
            }
        }
        send_packet(packet);
    }
}

vector<bool> receive_message(vector<vector<bool>> R) 
{
    rep(i,31)
    {
        is_ok[i] = 0;
        was_one[i] = 0;
        nxt_not[i] = 0;
    }
    rep(i,31) nxt_not[i] = (i+1)%31;
    forall(it,R)
    {
        rep(i,31)
        {
            if(!was_one[i])
            {
                if(it[i] == 0) nxt_not[i] = (nxt_not[i]+1)%31;
                else was_one[i] = 1;
            }
        }
    }
    rep(i,31)
    {
        int cur_v = i;
        rep(j,31) odw[j] = 0;
        int siz_ = 0;
        vi v;
        while(odw[cur_v] == 0)
        {
            v.pb(cur_v);
            siz_++;
            odw[cur_v] = 1;
            cur_v = nxt_not[cur_v];
        }
        if(siz_ == 16)
        {
            forall(it,v) is_ok[it] = 1;
            break;
        }
    }
    vector<bool> ans;
    rep(i,31) was_one[i] = 0;
    forall(it,R)
    {
        rep(bit,31)
        {
            if(!is_ok[bit]) continue;
            if(!was_one[bit])
            {
                if(it[bit] == 1) was_one[bit] = 1;
            }
            else 
            {
                ans.pb(it[bit]);
            }
        }
    }
    int siz_ = 1024;
    rep(i,siz(ans))
    {
        if(ans[i] == 1) break;
        siz_--;
    }
    vector<bool> ans2;
    rep2(i,1025-siz_,siz(ans)-1) ans2.pb(ans[i]);
    return ans2;
}

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