Submission #1194721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194721		tutis	Message (IOI24_message)	C++20	0 / 100	3499 ms	1144 KiB

message

#include "message.h"
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
#include <math.h>

using namespace std;

vector<bool> masks[2100];

int counter = 0;

void init()
{
    counter = 0;
    mt19937_64 rng(651651651);
    for (int i = 0; i < 2100; i++)
    {
        masks[i] = vector<bool>(31);
        for (int j = 0; j < 31; j++)
        {
            masks[i][j] = rng() % 2;
        }
    }
}

struct X
{
    vector<int> maybeC;
    vector<int> C;
};

vector<bool> send(vector<bool> A)
{
    for (int j = 0; j < 31; j++)
    {
        A[j] = A[j] ^ masks[counter][j];
    }
    vector<bool> received = send_packet(A);
    for (int j = 0; j < 31; j++)
    {
        received[j] = received[j] ^ masks[counter][j];
    }
    counter++;
    return received;
}

void decode(X *x, vector<bool> msg)
{
    vector<int> maybeC;
    for (int v : x->maybeC)
    {
        if (msg[v])
        {
            x->C.push_back(v);
        }
        else
        {
            maybeC.push_back(v);
        }
    }
    x->maybeC = maybeC;
}

vector<bool> globC;

void send_message(vector<bool> M, vector<bool> C)
{
    globC = C;
    mt19937_64 rng(89168918691);
    init();
    X x;
    for (int i = 0; i < 31; i++)
    {
        x.maybeC.push_back(i);
    }
    while (x.C.size() < 15)
    {
        vector<bool> to_send(31);
        for (int v : x.maybeC)
        {
            if (C[v])
            {
                to_send[v] = rng() % 2;
            }
            else
            {
                to_send[v] = 0;
            }
        }
        vector<bool> received = send(to_send);
        decode(&x, received);
    }
    vector<int> good = x.maybeC;
    int offset = 16-(int(M.size()) + 4) % 16;
    vector<bool> X;
    for (int t = 0; t < 4; t++)
    {
        X.push_back(offset % 2);
        offset /= 2;
    }
    for (int v : M)
    {
        X.push_back(v);
    }
    int i = 0;
    while (i < X.size())
    {
        vector<bool> packet(31);
        for (int v : good)
        {
            if (i < X.size())
            {
                packet[v] = X[i];
                i++;
            }
        }
        send(packet);
    }
}

std::vector<bool> receive_message(vector<vector<bool>> R)
{
    init();
    for (int i = 0; i < R.size(); i++)
    {
        for (int j = 0; j < 31; j++)
        {
            R[i][j] = R[i][j] ^ masks[i][j];
        }
    }
    X x;
    for (int i = 0; i < 31; i++)
    {
        x.maybeC.push_back(i);
    }
    int i = 0;
    while (x.C.size() < 15)
    {
        decode(&x, R[i]);
        i++;
    }
    vector<int> good = x.maybeC;
    vector<int> X;
    for (; i < R.size(); i++)
    {
        for (int v : good)
        {
            X.push_back(R[i][v]);
        }
    }
    int offset = 0;
    for (int i = 0; i < 4; i++)
    {
        if (X[i])
        {
            offset += 1 << i;
        }
    }
    vector<bool> answer;
    for (int i = 4; i < X.size() - offset; i++)
    {
        answer.push_back(X[i]);
    }
    return answer;
}

// vector<vector<bool>> sent;

// int main()
// {
//     vector<bool> msg = {0, 1, 1, 0,0,0,0,0,1,1,1,1,0,0,0,0};
//     send_message(msg,
//                  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
//                   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1});
//     vector<bool> received = receive_message(sent);
//     for (int v : received)
//     {
//         cout << v << " ";
//     }
//     cout << "\n";
// }

// mt19937_64 rng(0);
// vector<bool> send_packet(std::vector<bool> A)
// {
//     for (int i = 0; i < 31; i++)
//     {
//         if (globC[i])
//         {
//             A[i] = rng() % 2;
//         }
//     }
//     sent.push_back(A);
//     return A;
// }

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