Submission #1194715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194715		Nelt	Message (IOI24_message)	C++20	100 / 100	392 ms	852 KiB

message

#include "message.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll a[31], used[31];

void send_message(vector<bool> a, vector<bool> c)
{
    reverse(a.begin(), a.end());
    a.push_back(1);
    while (a.size() < 1025) a.push_back(0);
    vector<vector<bool>> send(66, vector<bool>(31));
    ll ptr = 0;
    for (ll i = 0; i < 31; i++) if (!c[i]) 
    {
        ll pos = (i + 1) % 31;
        while (c[pos]) pos = (pos + 1) % 31;
        send[(pos - i + 31) % 31 - 1][i] = 1;
        for (ll j = (pos - i + 31) % 31; j < 66; j++) send[j][i] = a[ptr++];
    }
    for (ll i = 0; i < 66; i++) send_packet(send[i]);
}
vector<bool> receive_message(vector<vector<bool>> send)
{
    vector<bool> ans(1025), c(31, 1);
    for (ll i = 0; i < 31; i++)
    {
        ll dist = 0;
        while (dist < 31 and send[dist][i] == 0) dist++;
        a[i] = (i + dist + 1) % 31;
    }
    vector<ll> fixed;
    vector<bool> used(31);
    for (ll i = 0; i < 31 and fixed.size() < 16; i++)
    {
        used.assign(31, 0);
        ll cur = a[i];
        fixed = {i};
        while (cur != i and !used[cur]) used[cur] = 1, fixed.push_back(cur), cur = a[cur];
        if (cur != i)
            fixed.clear();
    }
    ll ptr = 0;
    for (ll i : fixed) c[i] = 0;
    for (ll i = 0; i < 31; i++) 
    if (!c[i])
    {
        ll pos = (i + 1) % 31;
        while (c[pos]) pos = (pos + 1) % 31;
        for (ll j = (pos - i + 31) % 31; j < 66; j++) ans[ptr++] = send[j][i];
    }
    while (ans.back() == 0) ans.pop_back();
    ans.pop_back();
    reverse(ans.begin(), ans.end());
    return ans;
}

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