Submission #603696

#	Time	Username	Problem	Language	Result	Execution time	Memory
603696		JeanBombeur	Flight to the Ford (BOI22_communication)	C++17	74 / 100	3801 ms	2032 KiB

communication

#include"communication.h"
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

//  <|°_°|>

//  M. Broccoli

const int LOG = 30;

pair <int, int> Dsu[LOG];

int Fixed[LOG];
int Ans[LOG];

int Find(int a) {
    return Dsu[a].first < 0 ? a : Find(Dsu[a].first);
}

int Path(int a) {
    return Dsu[a].first < 0 ? 0 : Dsu[a].second ^ Path(Dsu[a].first);
}

void Union(int a, int b, int link) {
    a = Find(a), b = Find(b);
    if (a == b)
        return;
    Dsu[a] = {b, link};
    return;
}

pair <int, int> DecodeStep(vector <int> &Bits) {
    vector <int> Poss(4);
    Poss[0] = Poss[1] = 1;
    Poss[2] = Poss[3] = 0;
    for (int i = 0; i < 4; i ++)
    {
        if (i && Bits[i] == Bits[i - 1])
        {
            Poss[Bits[i] ^ 1] --;
            if (i == 2)
            {
                Poss[2 ^ Bits[i]] ++;
                Poss[3 ^ Bits[i]] -= 42;
            }
            else
                Poss[3 ^ Bits[i]] ++;
        }
    }
    vector <int> ans;
    for (int i = 0; i < 4; i ++)
    {
        if (Poss[i] > 0)
            ans.push_back(i);
    }
    if (ans.size() == 1)
        return {ans[0], ans[0]};
    return {ans[0], ans[1]};
}

pair <int, int> EncodeStep(int a) {
    vector <int> ToSend(4, 0);
    if (a == 0)
        ToSend = {0, 0, 0, 0};
    if (a == 1)
        ToSend = {1, 1, 1, 1};
    if (a == 2)
        ToSend = {1, 0, 0, 1};
    if (a == 3)
        ToSend = {0, 1, 1, 0};
    for (int i = 0; i < 4; i ++)
    {
        ToSend[i] = send(ToSend[i]);
    }
    return DecodeStep(ToSend);
}

int Log(int n) {
    return n == 1 ? 0 : 1 + Log(n / 2);
}

void encode(int nbMessages, int message) {
    message --;
    fill_n(Fixed, LOG, 0);
    fill_n(Dsu, LOG, make_pair(-1, 0));
    int last = 0;
    for (int i = 1; (1 << i) < nbMessages; i ++)
    {
        int cur = (message >> i) & 1;
        int bit = (message >> last) & 1;
        pair <int, int> x = EncodeStep(2 * cur + bit);
        if ((x.first & 1) == (x.second & 1))
            Fixed[Find(last)] = 1;
        if ((x.first & 2) == (x.second & 2))
            Fixed[Find(i)] = 1;
        if ((x.first ^ x.second) == 3)
            Union(i, last, 0);
        while (Fixed[Find(last)] == 1 && last < i)
            last ++;
    }
    return;
}

pair <int, int> decode(int nbMessages) {
    fill_n(Fixed, LOG, 0);
    fill_n(Dsu, LOG, make_pair(-1, 0));
    fill_n(Ans, LOG, -1);
    vector <int> Read(4, 0);
    int last = 0;
    for (int i = 1; (1 << i) < nbMessages; i ++)
    {
        for (int j = 0; j < 4; j ++)
        {
            Read[j] = receive();
        }
        pair <int, int> x = DecodeStep(Read);
        if ((x.first & 1) == (x.second & 1))
        {
            Fixed[Find(last)] = 1;
            Ans[last] = x.first & 1;
        }
        if ((x.first & 2) == (x.second & 2))
        {
            Fixed[Find(i)] = 1;
            Ans[i] = (x.first >> 1) & 1;
        }
        if ((x.first ^ x.second) == 3)
            Union(i, last, (x.first & 1) ^ (x.first & 2));
        while (Fixed[Find(last)] == 1 && last < i)
            last ++;
    }
    for (int i = 0; (1 << i) < nbMessages; i ++)
    {
        if (Ans[i] >= 0)
            Ans[Find(i)] = Path(i) ^ Ans[i];
    }
    int both = -1;
    for (int i = 0; (1 << i) < nbMessages; i ++)
    {
        if (Ans[Find(i)] < 0)
            both = Find(i);
    }
    pair <int, int> ans = {1, 1};
    if (both >= 0)
        Ans[both] = 0;
    for (int i = 0; (1 << i) < nbMessages; i ++)
    {
        Ans[i] = Path(i) ^ Ans[Find(i)];
    }
    for (int i = 0; (1 << i) < nbMessages; i ++)
    {
        ans.first += Ans[i] << i;
    }
    Ans[both] = 1;
    for (int i = 0; (1 << i) < nbMessages; i ++)
    {
        Ans[i] = Path(i) ^ Ans[Find(i)];
    }
    for (int i = 0; (1 << i) < nbMessages; i ++)
    {
        ans.second += Ans[i] << i;
    }
    ans.first = min(ans.first, nbMessages);
    ans.second = min(ans.second, nbMessages);
    return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 59.00003 / 85