답안 #603944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603944 2022-07-24T13:46:23 Z JeanBombeur Flight to the Ford (BOI22_communication) C++17
100 / 100
3494 ms 2032 KB
#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)]};
}
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1784 KB Output is correct
2 Correct 14 ms 1748 KB Output is correct
3 Correct 16 ms 1760 KB Output is correct
4 Correct 9 ms 1736 KB Output is correct
5 Correct 10 ms 1740 KB Output is correct
6 Correct 32 ms 1788 KB Output is correct
7 Correct 43 ms 1696 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 731 ms 1824 KB Output is correct
2 Correct 270 ms 1908 KB Output is correct
3 Correct 445 ms 1728 KB Output is correct
4 Correct 819 ms 1684 KB Output is correct
5 Correct 732 ms 1684 KB Output is correct
6 Correct 547 ms 1688 KB Output is correct
7 Correct 2303 ms 1724 KB Output is correct
8 Correct 3494 ms 2032 KB Output is correct
9 Correct 3272 ms 1976 KB Output is correct
10 Correct 2775 ms 1816 KB Output is correct
11 Correct 2882 ms 1940 KB Output is correct
12 Correct 2820 ms 1928 KB Output is correct
13 Correct 3103 ms 1828 KB Output is correct
14 Correct 2830 ms 1968 KB Output is correct
15 Correct 1622 ms 1792 KB Output is correct
16 Correct 3408 ms 1736 KB Output is correct
17 Correct 817 ms 1876 KB Output is correct
18 Correct 782 ms 1772 KB Output is correct
19 Correct 805 ms 1808 KB Output is correct
20 Correct 794 ms 1740 KB Output is correct
21 Correct 876 ms 1856 KB Output is correct
22 Correct 880 ms 1732 KB Output is correct
23 Correct 1372 ms 1820 KB Output is correct
24 Correct 13 ms 1656 KB Output is correct
25 Correct 14 ms 1716 KB Output is correct
26 Correct 15 ms 1752 KB Output is correct
27 Correct 12 ms 1884 KB Output is correct
28 Correct 17 ms 1764 KB Output is correct
29 Correct 29 ms 1860 KB Output is correct
30 Correct 45 ms 1744 KB Output is correct