Submission #1106303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106303		jerzyk	Message (IOI24_message)	C++17	100 / 100	1173 ms	1108 KiB

message

#include <bits/stdc++.h>
#include "message.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 1000 * 1000 + 7;
int xddd[40];
int jp[40];
vector<bool> M;
int il = 0, cnt = 0;

bool Nxt()
{
    if(cnt >= (int)M.size()) return 0;
    return M[cnt++];
}

void send_message(vector<bool> _M, vector<bool> C)
{
    il = 0; cnt = 0;
    
    M.clear();
    _M.pb(1);
    M = _M;
    vector<int> pos, dis;
    vector<bool> bas(31, false);
    vector<vector<bool>> answer(100, bas);

    for(int i = 0; i < (int)C.size(); ++i)
        if(C[i] == 0)
            pos.pb(i);
    for(int i = 0; i < 16; ++i)
    {
        int d;
        if(i < 15)
            d = pos[i + 1] - pos[i];
        else
            d = 31 + pos[0] - pos[i];
        dis.pb(d);
        answer[d - 1][pos[i]] = true;
        il = max(il, d - 1);
    }
    for(int l = 0; cnt < (int)M.size(); ++l)
    {
        il = max(il, l);
        for(int i = 0; i < 16; ++i)
            if(dis[i] < l + 1)
                answer[l][pos[i]] = Nxt();
    }
    while((int)answer.size() > il + 1)
        answer.pop_back();
    for(int i = 0; i < (int)answer.size(); ++i)
        send_packet(answer[i]);
}

vector<bool> receive_message(vector<vector<bool>> R)
{
    il = 0; cnt = 0;
    vector<int> pos, dis;
    vector<bool> ans;
    for(int i = 1; i < 35; ++i)
    {
        jp[i] = 0; xddd[i] = 0;
    }
    for(int i = 0; i < 31; ++i)
    {
        int d = 1, l = 0;
        while(l < (int)R.size() && R[l][i] != 1)
            {++l; ++d;}
        xddd[i] = d;
        jp[i] = (i + d) % 31;
    }
    for(int i = 0; i < 31; ++i)
    {
        int d = 1, v = jp[i];
        while(v != i && d < 17)
        {
            ++d;
            v = jp[v];
        }
        if(d == 16)
        {
            dis.pb(xddd[i]);
            pos.pb(i);
        }
    }
    for(int l = 0; l < (int)R.size(); ++l)
        for(int i = 0; i < (int)pos.size(); ++i)
            if(dis[i] < l + 1)
                ans.pb(R[l][pos[i]]);
    while(ans.back() == 0)
        ans.pop_back();
    ans.pop_back();
    return ans;
}

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