Submission #603639

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
603639	2022-07-24T09:14:38 Z	JeanBombeur	Flight to the Ford (BOI22_communication)	C++17	15 / 100	477 ms	1860 KB

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);
    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[last] = 1;
        if ((x.first & 2) == (x.second & 2))
            Fixed[i] = 1;
        while (Fixed[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[last] = 1;
            Ans[last] = x.first & 1;
        }
        if ((x.first & 2) == (x.second & 2))
        {
            Fixed[i] = 1;
            Ans[i] = (x.first >> 1) & 1;
        }
        if ((x.first & 1) != (x.second & 1))
        {
            if ((x.first & 2) != (x.second & 2))
                Union(i, last, (x.first & 1) ^ (x.first & 2));
        }
        while (Fixed[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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1860 KB	Output is correct
2	Correct	15 ms	1712 KB	Output is correct
3	Correct	17 ms	1736 KB	Output is correct
4	Correct	12 ms	1840 KB	Output is correct
5	Correct	19 ms	1704 KB	Output is correct
6	Correct	34 ms	1808 KB	Output is correct
7	Correct	44 ms	1688 KB	Output is correct

Subtask #2

0.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	477 ms	200 KB	Not correct
2	Halted	0 ms	0 KB	-