제출 #1195006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195006		tutis	메시지 (IOI24_message)	C++20	66.69 / 100	1309 ms	900 KiB

message

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

using namespace std;

int counter = 0;

const int bitsCnt = 10;
bitset<31> seqs[1 << bitsCnt];
bitset<31> masks[200];
const int64_t seed1 = 5;
int tests = 10000;

bitset<31> globC;

vector<bitset<16>> safeMasks{
    0b0000000011111111,
    0b1111111100000000,
    0b1111000011110000,
    0b1100110011001100,
    0b1010101010101010,
    0b0101010101010101};

bitset<6> recov(bitset<11> x)
{
    bitset<6> ret;
    for (int t = 0; t < 6; t++)
    {
        ret[t] = true;
        for (int i = 0; i < 11; i++)
        {
            if (x[i] && safeMasks[t][i])
            {
                ret[t] = !ret[t];
            }
        }
    }
    return ret;
}
bitset<11> recover(bitset<17> x, int *flip)
{
    for (int i = -1; i < 17; i++)
    {
        if (i != -1)
        {
            x[i] = x[i] ^ true;
        }
        bitset<11> v = x.to_ullong();
        bitset<6> rec = x.to_ullong() >> 11;
        if (recov(v) == rec)
        {
            *flip = i;
            return v;
        }
        if (i != -1)
        {
            x[i] = x[i] ^ true;
        }
    }
    *flip = -2;
    return {};
}

bool initialized = false;

void init()
{
    counter = 0;
    if (!initialized)
    {
        mt19937_64 rng(seed1);
        for (int i = 0; i < (1 << bitsCnt); i++)
        {
            seqs[i] = bitset<31>(rng());
            if (i % 2 == 1)
            {
                seqs[i] = ~seqs[i - 1];
            }
        }
        for (int i = 0; i < 200; i++)
        {
            for (int j = 0; j < 31; j++)
            {
                masks[i] = rng();
            }
        }
    }
    initialized = true;
}

bitset<31> send(bitset<31> A)
{
    if (counter >= 199)
    {
        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;
}

deque<bool> prepareBits(vector<bool> M)
{
    int offset = 1024 - M.size();
    deque<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);
    }
    while (!X.empty() && X.back() == 0)
    {
        X.pop_back();
    }
    return X;
}

vector<bitset<31>> getSeqs(X x)
{
    vector<bitset<31>> ret;
    for (bitset<31> v : seqs)
    {
        bool ok = true;
        for (bitset<31> w : ret)
        {
            if (v == w)
            {
                continue;
            }
            int possibleDiffs = ((v ^ w) & (~x.C)).count();
            int possibleChanges = 15 - x.C.count();
            if (possibleChanges * 2 >= possibleDiffs)
            {
                ok = false;
                break;
            }
        }
        if (ok)
        {
            ret.push_back(v);
        }
    }
    int v = 1;
    while (v * 2 <= int(ret.size()))
    {
        v *= 2;
    }
    while (int(ret.size()) > v)
    {
        ret.pop_back();
    }
    return ret;
}

int sends = 0;

void send_message(vector<bool> M, vector<bool> Cvect)
{
    sends++;
    mt19937_64 rng(sends);
    init();
    bitset<31> C;
    for (int i = 0; i < 31; i++)
    {
        C[i] = Cvect[i];
    }
    globC = C;
    X x;
    deque<bool> X = prepareBits(M);
    while (x.C.count() < 14)
    {
        vector<bitset<31>> seqs = getSeqs(x);
        int s = 0;
        for (int i = 0; (1 << (i + 1)) <= seqs.size(); i++)
        {
            if (!X.empty() && X[0])
            {
                s += 1 << i;
            }
            if (!X.empty())
            {
                X.pop_front();
            }
        }
        bitset<31> to_send = seqs[s];
        for (int i = 0; i < 31; i++)
        {
            if (C[i])
            {
                to_send[i] = rng() % 2;
            }
        }
        bool ok = false;
        bitset<31> resp = send(to_send);
        int s1 = 0;
        int ss = 0;
        for (bitset<31> seq : seqs)
        {
            bitset<31> diff = (resp ^ seq) | (x.C);
            if (diff.count() >= 16)
            {
                s1++;
                continue;
            }
            if (ok)
            {
                bitset<31> seq1 = seqs[s1];
                bitset<31> diff1 = (resp ^ seq) | (x.C);
                bitset<31> dx = (seq ^ seq1) & (~x.C);
                if ((diff & dx).count() >= (diff1 & dx).count())
                {
                    s1++;
                    continue;
                }
            }
            ok = true;
            ss = s1;
            s1++;
        }
        x.C = (resp ^ seqs[ss]) | (x.C);
        if (s != ss)
        {
            exit(0);
        }
        if (!ok)
        {
            exit(0);
        }

        if (counter > 100)
        {
            exit(0);
        }
    }

    while (x.C.count() == 14)
    {
        bitset<17> xx;
        for (int i = 0; i < 11; i++)
        {
            if (!X.empty())
            {
                xx[i] = X[0];
                X.pop_front();
            }
        }
        bitset<6> y = recov(xx.to_ullong());
        xx |= (bitset<17>(y.to_ullong()) << 11);
        bitset<31> to_send;
        int c = 0;
        for (int i = 0; i < 31; i++)
        {
            if (x.C[i] == false)
            {
                to_send[i] = xx[c];
                c++;
            }
        }
        for (int i = 0; i < 31; i++)
        {
            if (C[i])
            {
                to_send[i] = rng() % 2;
            }
        }
        bitset<17> xx_resp;
        bitset<31> resp = send(to_send);
        c = 0;
        for (int i = 0; i < 31; i++)
        {
            if (x.C[i] == false)
            {
                xx_resp[c] = resp[i];
                c++;
            }
        }
        int flip;
        recover(xx_resp, &flip);
        if (flip == -2)
        {
            exit(0);
        }
        c = 0;
        for (int i = 0; i < 31; i++)
        {
            if (x.C[i] == false)
            {
                if (c == flip)
                {
                    x.C[i] = true;
                    break;
                }
                c++;
            }
        }
    }

    bitset<31> good = x.C.flip();
    while (!X.empty())
    {
        bitset<31> packet;
        for (int v = 0; v < 31; v++)
        {
            if (good[v])
            {
                if (!X.empty())
                {
                    packet[v] = X[0];
                    X.pop_front();
                }
            }
        }
        send(packet);
    }
}

std::vector<bool> receive_message(vector<vector<bool>> Rvect)
{
    init();
    vector<bitset<31>> R(Rvect.size());
    for (int i = 0; i < int(Rvect.size()); i++)
    {
        bitset<31> b;
        for (int j = 0; j < 31; j++)
        {
            b[j] = Rvect[i][j];
        }
        R[i] = b;
    }
    for (int i = 0; i < int(R.size()); i++)
    {
        R[i] = R[i] ^ masks[i];
    }
    vector<bool> recX;
    X x;
    int i = 0;
    while (x.C.count() < 14)
    {
        bitset<31> resp = R[i];
        i++;
        vector<bitset<31>> seqs = getSeqs(x);
        int s1 = 0;
        int ss = 0;
        bool ok = false;
        for (bitset<31> seq : seqs)
        {
            bitset<31> diff = (resp ^ seq) | (x.C);
            if (diff.count() >= 16)
            {
                s1++;
                continue;
            }
            if (ok)
            {
                bitset<31> seq1 = seqs[s1];
                bitset<31> diff1 = (resp ^ seq) | (x.C);
                bitset<31> dx = (seq ^ seq1) & (~x.C);
                if ((diff & dx).count() >= (diff1 & dx).count())
                {
                    s1++;
                    continue;
                }
            }
            ok = true;
            ss = s1;
            s1++;
        }
        x.C = (resp ^ seqs[ss]) | (x.C);
        if (!ok)
        {
            exit(0);
        }
        vector<bool> a;
        for (int i = 0; (1 << (i + 1)) <= seqs.size(); i++)
        {
            if ((ss & (1 << i)) != 0)
            {
                recX.push_back(true);
            }
            else
            {
                recX.push_back(false);
            }
        }
    }

    while (x.C.count() == 14)
    {
        bitset<17> xx_resp;
        bitset<31> resp = R[i];
        i++;
        int c = 0;
        for (int i = 0; i < 31; i++)
        {
            if (x.C[i] == false)
            {
                xx_resp[c] = resp[i];
                c++;
            }
        }
        int flip;
        bitset<11> recovered = recover(xx_resp, &flip);
        if (flip == -2)
        {
            exit(0);
        }
        for (int i = 0; i < 11; i++)
        {
            recX.push_back(recovered[i]);
        }
        c = 0;
        for (int i = 0; i < 31; i++)
        {
            if (x.C[i] == false)
            {
                if (c == flip)
                {
                    x.C[i] = true;
                    break;
                }
                c++;
            }
        }
    }

    bitset<31> good = x.C.flip();
    for (; i < int(R.size()); i++)
    {
        for (int v = 0; v < 31; v++)
        {
            if (good[v])
            {
                recX.push_back(R[i][v]);
            }
        }
    }
    int offset = 0;
    while (offset < int(recX.size()) && recX[offset])
    {
        offset++;
    }
    vector<bool> answer;
    for (int i = offset + 1; i < int(recX.size()); i++)
    {
        answer.push_back(recX[i]);
    }
    while (answer.size() < 1025)
    {
        answer.push_back(0);
    }
    while ((1024 - int(answer.size())) != offset && answer.size() > 0)
    {
        answer.pop_back();
    }
    return answer;
}

// vector<vector<bool>> sent;

// int main()
// {
//     mt19937_64 rng(5);
//     int maxQ = 0;
//     double avg = 0;
//     for (int i = 0; i < tests; i++)
//     {
//         vector<bool> msg(1024);
//         for (int i = 0; i < int(msg.size()); i++)
//         {
//             msg[i] = rng() % 2;
//         }
//         vector<bool> Cvect{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};
//         shuffle(Cvect.begin(), Cvect.end(), rng);
//         send_message(msg,
//                      Cvect);
//         vector<bool> received = receive_message(sent);
//         maxQ = max(maxQ, int(sent.size()));
//         avg += sent.size();
//         if (msg != received)
//         {
//             cout << "maxQ: " << maxQ << " i: " << i << endl;
//             cout << "mismatch!" << endl;
//             for (int i : msg)
//             {
//                 cout << i;
//             }
//             cout << endl;
//             for (int i : received)
//             {
//                 cout << i;
//             }
//             cout << endl;
//             exit(0);
//         }
//         else
//         {
//         }
//         sent = {};
//     }
//     cout << maxQ << " " << avg / tests << endl;
// }

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