oj.uz

답안 #603941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603941 2022-07-24T13:43:46 Z JeanBombeur Flight to the Ford (BOI22_communication) C++17
0 / 100
 3306 ms 1980 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});
    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});
    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
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 200 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 1740 KB Output is correct
2 Correct 176 ms 1672 KB Output is correct
3 Correct 501 ms 1680 KB Output is correct
4 Correct 840 ms 1724 KB Output is correct
5 Correct 677 ms 1780 KB Output is correct
6 Correct 562 ms 1736 KB Output is correct
7 Correct 2113 ms 1732 KB Output is correct
8 Correct 3306 ms 1980 KB Output is correct
9 Correct 2622 ms 1792 KB Output is correct
10 Correct 2885 ms 1932 KB Output is correct
11 Correct 2735 ms 1904 KB Output is correct
12 Correct 2820 ms 1812 KB Output is correct
13 Correct 3011 ms 1868 KB Output is correct
14 Correct 2932 ms 1856 KB Output is correct
15 Correct 1503 ms 1724 KB Output is correct
16 Correct 3200 ms 1764 KB Output is correct
17 Correct 844 ms 1748 KB Output is correct
18 Correct 881 ms 1736 KB Output is correct
19 Correct 848 ms 1768 KB Output is correct
20 Correct 736 ms 1828 KB Output is correct
21 Correct 875 ms 1812 KB Output is correct
22 Correct 772 ms 1884 KB Output is correct
23 Correct 1259 ms 1876 KB Output is correct
24 Incorrect 3 ms 220 KB Not correct
25 Halted 0 ms 0 KB -