제출 #1194951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194951		tutis	메시지 (IOI24_message)	C++20	컴파일 에러	0 ms	0 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 <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 = 4;
int tests = 1000;
bool initialized = false;

bitset<31> globC;

mt19937_64 rng;

void init(bitset<31> seed)
{
    rng = mt19937_64(seed.to_ullong());
    counter = 0;
    if (!initialized)
    {
        mt19937_64 rng(seed.to_ullong() ^ seed1);
        seqs[0] = bitset<31>(0);
        for (int i = 0; i < 31; i += 2)
        {
            seqs[2][i] = 1;
        }
        for (int i = 4; i < (1 << bitsCnt); i+=2)
        {
            while (seqs[i].count() != 15)
            {
                seqs[i] = bitset<31>(rng());
            }
        }
        for (int i = 1; i < (1 << bitsCnt); i += 2)
        {
            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 > 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;
}

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);
    }
    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 (ret.size() > v)
    {
        ret.pop_back();
    }
    return ret;
}

int sends = 0;

void send_message(vector<bool> M, vector<bool> Cvect)
{
    bitset<31> seed;
    sends++;
    mt19937_64 rng(sends);
    // vector<bool> seed_gen(31);
    // for (int i = 0; i < 31; i++)
    // {
    //     seed_gen[i] = rng() % 2;
    // }
    // seed_gen = send_packet(seed_gen);
    // for (int i = 0; i < 31; i++)
    // {
    //     seed[i] = seed_gen[i];
    // }
    init(seed);
    bitset<31> C;
    for (int i = 0; i < 31; i++)
    {
        C[i] = Cvect[i];
    }
    globC = C;
    X x;
    deque<bool> X = prepareBits(M);
    int step = 0;
    while (x.C.count() < 15)
    {
        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);
        }
    }
    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)
{
    bitset<31> seed;
    // for (int i = 0; i < 31; i++)
    // {
    //     seed[i] = Rvect[0][i];
    // }
    // Rvect.erase(Rvect.begin());
    init(seed);
    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;
    }
    for (int i = 0; i < R.size(); i++)
    {
        R[i] = R[i] ^ masks[i];
    }
    vector<bool> recX;
    X x;
    int i = 0;
    while (x.C.count() < 15)
    {
        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);
            }
        }
    }
    bitset<31> good = x.C.flip();
    for (; i < R.size(); i++)
    {
        for (int v = 0; v < 31; v++)
        {
            if (good[v])
            {
                recX.push_back(R[i][v]);
            }
        }
    }
    int offset = 0;
    while (offset < recX.size() && recX[offset])
    {
        offset++;
    }
    vector<bool> answer;
    for (int i = offset + 1; i < 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(3);
    int maxQ = 0;
    double avg = 0;
    for (int i = 0; i < tests; i++)
    {
        vector<bool> msg(100);
        for (int i = 0; i < 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;
}

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;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccoOZpfw.o: in function `send_packet(std::vector<bool, std::allocator<bool> >)':
stub.cpp:(.text+0x250): multiple definition of `send_packet(std::vector<bool, std::allocator<bool> >)'; /tmp/ccn3msAL.o:message.cpp:(.text+0x1580): first defined here
/usr/bin/ld: /tmp/ccoOZpfw.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccn3msAL.o:message.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status