Submission #603944

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

communication

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

//  <|°_°|>

//  M. Broccoli

struct segments_set {
    vector <pair <int, int>> Segments;
    
    void push_back(pair <int, int> a) {
        Segments.push_back(a);
        return;
    }
    
    int sum() {
        int ans = 0;
        for (pair <int, int> a : Segments)
            ans += a.second - a.first;
        return ans;
    }
    
    pair <segments_set, segments_set> split(int up) {
        int cut = (sum() + up) / 2;
        int cur = 0;
        pair <segments_set, segments_set> ans;
        int fill = 0;
        for (pair <int, int> a : Segments)
        {
            if (!fill && cur + a.second - a.first > cut)
            {
                if (cur == cut)
                    ans.second.push_back(a);
                else
                {
                    int opt = a.first + cut - cur;
                    ans.first.push_back({a.first, opt});
                    ans.second.push_back({opt, a.second});
                }
                fill = 1;
            }
            else
            {
                if (fill)
                    ans.second.push_back(a);
                else
                    ans.first.push_back(a);
            }
            cur += a.second - a.first;
        }
        return ans;
    }
    
    bool contain(int target) {
        for (pair <int, int> a : Segments)
        {
            if (a.first <= target && target < a.second)
                return true;
        }
        return false;
    }
    
    void merge(segments_set s) {
        for (pair <int, int> a : s.Segments)
            Segments.push_back(a);
        return;
    }
};

pair <int, int> DecodeStep() {
    vector <int> Poss(4);
    vector <int> Bits(4);
    Poss[0] = Poss[1] = 1;
    Poss[2] = Poss[3] = 0;
    for (int i = 0; i < 4; i ++)
    {
        Bits[i] = receive();
        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]};
}

void 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 ++)
    {
        send(ToSend[i]);
    }
    return;
}

void encode(int nbMessages, int message) {
    segments_set correct;
    segments_set incorrect;
    correct.push_back({1, nbMessages + 1});
    while (correct.sum() + incorrect.sum() > 4)
    {
        pair <segments_set, segments_set> nvCorr = correct.split(1);
        pair <segments_set, segments_set> nvIncorr = incorrect.split(0);
        int x;
        if (nvCorr.first.contain(message) || nvIncorr.first.contain(message))
            x = send(1);
        else
            x = send(0);
        if (x == 1)
        {
            correct = nvCorr.first;
            correct.merge(nvIncorr.first);
            incorrect = nvCorr.second;
        }
        else
        {
            correct = nvCorr.second;
            correct.merge(nvIncorr.second);
            incorrect = nvCorr.first;
        }
    }
    vector <int> poss;
    for (pair <int, int> a : correct.Segments)
    {
        for (int i = a.first; i < a.second; i ++)
            poss.push_back(i);
    }
    for (pair <int, int> a : incorrect.Segments)
    {
        for (int i = a.first; i < a.second; i ++)
            poss.push_back(i);
    }
    for (int i = 0; i < (int)poss.size(); i ++)
    {
        if (message == poss[i])
            EncodeStep(i);
    }
    return;
}

pair <int, int> decode(int nbMessages) {
    segments_set correct;
    segments_set incorrect;
    correct.push_back({1, nbMessages + 1});
    while (correct.sum() + incorrect.sum() > 4)
    {
        pair <segments_set, segments_set> nvCorr = correct.split(1);
        pair <segments_set, segments_set> nvIncorr = incorrect.split(0);
        if (receive() == 1)
        {
            correct = nvCorr.first;
            correct.merge(nvIncorr.first);
            incorrect = nvCorr.second;
        }
        else
        {
            correct = nvCorr.second;
            correct.merge(nvIncorr.second);
            incorrect = nvCorr.first;
        }
    }
    vector <int> poss;
    for (pair <int, int> a : correct.Segments)
    {
        for (int i = a.first; i < a.second; i ++)
            poss.push_back(i);
    }
    for (pair <int, int> a : incorrect.Segments)
    {
        for (int i = a.first; i < a.second; i ++)
            poss.push_back(i);
    }
    pair <int, int> x = DecodeStep();
    return {poss[min(x.first, (int)poss.size() - 1)], poss[min(x.second, (int)poss.size() - 1)]};
}

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