Submission #1194777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194777		tutis	메시지 (IOI24_message)	C++20	49.61 / 100	443 ms	896 KiB

message

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

using namespace std;

bitset<31> masks[110];

int counter = 0;

bool initialized = false;

const int64_t seed1 = 12312517312312563;
const int64_t seed2 = 18916130165158981;
const int64_t seed3 = 18916130165158981;

void init()
{
    counter = 0;
    if (!initialized)
    {
        mt19937_64 rng(seed1);
        for (int i = 0; i < 110; i++)
        {
            for (int j = 0; j < 31; j++)
            {
                masks[i][j] = rng() % 2;
            }
        }
        initialized = true;
    }
}

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

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

void decode(X *x, bitset<31> 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;

mt19937_64 rng(seed2);

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

std::vector<bool> receive_message(vector<vector<bool>> Rvect)
{
    vector<bitset<31>>R(Rvect.size());
    for (int i = 0; i < Rvect.size(); i++){
        bitset<31>b;
        for(int j=0;j<31;j++){
            b[j] = Rvect[i][j];
        }
        R[i]=b;
    }
    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;
    while (X[offset])
    {
        offset++;
    }
    vector<bool> answer;
    for (int i = offset + 1; i < X.size(); i++)
    {
        answer.push_back(X[i]);
    }
    while ((1024 - answer.size()) % 16 != offset)
    {
        answer.pop_back();
    }
    return answer;
}

// vector<vector<bool>> sent;

// int main()
// {
//     vector<bool> msg(1024);

//     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);

//     cout << "Q = " << sent.size() << endl;
//     if (msg != received)
//     {
//         cout << "mismatch!" << endl;
//     }
//     else
//     {
//         cout << "ok" << endl;
//     }
// }

// 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: 10 / 10
• Subtask 2: 39.6114 / 90