Submission #1311665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311665		cologne	Message (IOI24_message)	C++20	10 / 100	377 ms	796 KiB

message

#include "message.h"

#include <algorithm>
#include <cassert>
#include <numeric>
using namespace std;

const int MAX_SIZE = 1024;
const int MSG_SIZE = 31;
const int MSG_COUNT = 66;
const int CYC_LENGTH = 16;

void send_message(vector<bool> M, vector<bool> C)
{
    assert(M.size() < MAX_SIZE);
    assert(C.size() == MSG_SIZE);

    vector<bool> msg(MAX_SIZE + 1 - M.size(), false);
    msg.back() = true;
    copy(M.begin(), M.end(), back_inserter(msg));
    assert(msg.size() == MAX_SIZE + 1);

    vector<int> nxt;
    for (int i = 0; i < MSG_SIZE; ++i)
        if (!C[i])
            nxt.push_back(i);

    vector<vector<bool>> to_send(MSG_COUNT, vector<bool>(31, false));
    int ptr = 0;
    for (int i = 0; i < (int)nxt.size(); ++i)
    {
        int edg = (nxt[(i + 1) % nxt.size()] - nxt[i] + MSG_SIZE) % MSG_SIZE;
        to_send[edg - 1][nxt[i]] = true;
        for (int j = edg; j < MSG_COUNT; ++j)
            to_send[j][nxt[i]] = msg[ptr++];
    }

    assert(ptr == MAX_SIZE + 1);
    for (const auto &x : to_send)
        send_packet(x);
}

vector<bool> receive_message(vector<vector<bool>> R)
{
    assert(R.size() == MSG_COUNT);

    vector<int> out(MSG_SIZE);
    iota(out.begin(), out.end(), 0);
    for (int i = 0; i < MSG_SIZE; ++i)
        for (int j = 0; j < MSG_COUNT; ++j)
        {
            out[i] = (out[i] + 1) % MSG_SIZE;
            if (R[j][i])
                break;
        }

    vector<bool> vis(MSG_SIZE);
    for (int i = 0; i < MSG_SIZE; ++i)
    {
        fill(vis.begin(), vis.end(), false);
        bool ok = true;
        int cur = i;
        for (int j = 0; j < CYC_LENGTH; ++j)
        {
            if (vis[cur])
            {
                ok = false;
                break;
            }
            vis[cur] = true;
            cur = out[cur];
        }
        if (cur != i)
            ok = false;
        if (ok)
            break;
    }

    vector<bool> ans;
    for (int i = 0; i < MSG_SIZE; ++i)
        if (vis[i])
        {
            bool true_encounter = false;
            for (int j = 0; j < MSG_COUNT; j++)
            {
                if (true_encounter)
                    ans.push_back(R[j][i]);
                if (R[j][i])
                    true_encounter = true;
            }
        }
    assert(ans.size() == MAX_SIZE + 1);
    auto one = find(ans.begin(), ans.end(), true);
    return vector<bool>(one + 1, ans.end());
}

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