Submission #1194810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194810		tutis	Message (IOI24_message)	C++20	49.61 / 100	2389 ms	2932 KiB

message

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include "message.h"
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <bitset>
#include <vector>
#include <assert.h>
#include <math.h>

using namespace std;

int counter = 0;
bool initialized = false;

const int bitsCnt = 16;
bitset<31> seqs[1 << bitsCnt];
bitset<31> masks[110];
const int64_t seed1 = 123125173141312563;
const int64_t seed2 = 981891681523456374;

bitset<31> globC;

mt19937_64 rng(0);

void init()
{
    counter = 0;
    if (!initialized)
    {
        mt19937_64 rng(seed1);
        initialized = true;
        for (int i = 0; i < (1 < bitsCnt); i++)
        {
            seqs[i] = i;
        }
        for (int i = 0; i < (1 << bitsCnt); i++)
        {
            for (int j = bitsCnt; j < 31; j++)
            {
                seqs[i][j] = seqs[i][j - bitsCnt];
            }
        }
        shuffle(seqs, seqs + (1 << bitsCnt), rng);

        for (int i = 0; i < 110; i++)
        {
            for (int j = 0; j < 31; j++)
            {
                masks[i] = rng();
            }
        }
    }
}

bitset<31> send(bitset<31> A)
{
    if (counter > 100)
    {
        assert(false);
    }
    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;
}

struct X
{
    bitset<31> C;
};

bool subset(bitset<31> a, bitset<31> b)
{
    return (a & b) == a;
}

X decode(X x, bitset<31> msg, bitset<31> bits)
{
    int i = (1 << bitsCnt) - 1;
    vector<int> options;
    for (bitset<31> sub = bits; i >= 0; sub = bits & bitset<31>(sub.to_ullong() - 1))
    {
        bitset<31> diff = msg ^ seqs[i];
        diff |= x.C;
        if (diff.count() > 15)
        {
            i--;
            continue;
        }
        if (!subset(bits & diff, sub))
        {
            i--;
            continue;
        }
        options.push_back(i);
        i--;
    }
    if (options.size() == 0)
    {
        exit(2);
    }
    bitset<31> diff;
    diff.flip();
    for (int i : options)
    {
        diff &= msg ^ seqs[i];
    }
    x.C |= diff;
    return x;
}

bitset<31> get_bits(int step, bitset<31> xC)
{
    mt19937_64 rng(step);
    bitset<31> ret;
    while (ret.count() > bitsCnt)
    {
        ret[rng() % 31] = false;
    }
    while (ret.count() < bitsCnt)
    {
        int i = rng() % 31;
        ret[i] = true;
    }
    return ret;
}

void send_message(vector<bool> M, vector<bool> Cvect)
{
    rng = mt19937_64(seed2);
    bitset<31> C;
    for (int i = 0; i < 31; i++)
    {
        C[i] = Cvect[i];
    }
    globC = C;
    init();
    X x;
    int step = 0;
    while (x.C.count() < 15)
    {
        bitset<31> bits = get_bits(step, x.C);
        int val = 0;
        int cnt = 0;
        for (int i = 0; i < 31; i++)
        {
            if (bits[i])
            {
                if (C[i])
                {
                    val += 1 << cnt;
                }
                cnt++;
            }
        }
        bitset<31> to_send = seqs[val % (1 << bitsCnt)];
        for (int i = 0; i < 31; i++)
        {
            if (C[i])
            {
                to_send[i] = rng() % 2;
            }
        }
        bitset<31> received = send(to_send);
        x = decode(x, received, bits);
        step++;
        if (counter >= 100)
        {
            assert(false);
        }
    }
    bitset<31> good = x.C.flip();
    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 = 0; v < 31; v++)
        {
            if (good[v])
            {
                if (i < X.size())
                {
                    packet[v] = X[i];
                    i++;
                }
            }
        }
        send(packet);
    }
}

std::vector<bool> receive_message(vector<vector<bool>> Rvect)
{
    rng = mt19937_64(seed2);
    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++)
    {
        R[i] = R[i] ^ masks[i];
    }
    X x;
    int i = 0;
    int step = 0;
    while (x.C.count() < 15 && i < R.size())
    {
        x = decode(x, R[i], get_bits(step, x.C));
        i++;
        step++;
    }
    bitset<31> good = x.C.flip();
    vector<int> X;
    for (; i < R.size(); i++)
    {
        for (int v = 0; v < 31; v++)
        {
            if (good[v])
            {
                X.push_back(R[i][v]);
            }
        }
    }
    int offset = 0;
    while (offset < X.size() && 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.size() > 0)
    {
        answer.pop_back();
    }
    return answer;
}

// vector<vector<bool>> sent;

// int main()
// {
//     for (int i = 0; i < 100; i++)
//     {
//         vector<bool> msg(1024);
//         for (int i = 0; i < msg.size(); i++)
//         {
//             msg[i] = rng() % 2;
//         }

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