제출 #1194760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194760		tutis	메시지 (IOI24_message)	C++20	49.61 / 100	460 ms	908 KiB

message

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

using namespace std;

vector<bool> masks[100];

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 < 100; i++)
        {
            masks[i] = vector<bool>(31);
            for (int j = 0; j < 31; j++)
            {
                masks[i][j] = rng() % 2;
            }
        }
        initialized = true;
    }
}

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

vector<bool> send(vector<bool> A)
{
    if (counter >= 100)
    {
        return 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;

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)
    {
        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 = (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())
    {
        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;
    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;

// mt19937_64 rng(seed3);
// 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