oj.uz

답안 #603696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603696 2022-07-24T09:50:33 Z JeanBombeur Flight to the Ford (BOI22_communication) C++17
74 / 100
 3801 ms 2032 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1748 KB Output is correct
2 Correct 11 ms 1744 KB Output is correct
3 Correct 21 ms 1780 KB Output is correct
4 Correct 13 ms 1736 KB Output is correct
5 Correct 15 ms 1684 KB Output is correct
6 Correct 36 ms 1828 KB Output is correct
7 Correct 48 ms 1664 KB Output is correct

Subtask #2
59.00003 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 965 ms 1676 KB Output is partially correct
2 Partially correct 346 ms 1728 KB Output is partially correct
3 Partially correct 545 ms 1672 KB Output is partially correct
4 Partially correct 938 ms 1736 KB Output is partially correct
5 Partially correct 699 ms 1672 KB Output is partially correct
6 Partially correct 507 ms 1684 KB Output is partially correct
7 Partially correct 2433 ms 1792 KB Output is partially correct
8 Partially correct 3407 ms 2032 KB Output is partially correct
9 Partially correct 3114 ms 1792 KB Output is partially correct
10 Partially correct 3122 ms 1912 KB Output is partially correct
11 Partially correct 3036 ms 1952 KB Output is partially correct
12 Partially correct 3011 ms 1880 KB Output is partially correct
13 Partially correct 3015 ms 1936 KB Output is partially correct
14 Partially correct 3093 ms 1800 KB Output is partially correct
15 Partially correct 1741 ms 1784 KB Output is partially correct
16 Partially correct 3801 ms 1720 KB Output is partially correct
17 Partially correct 689 ms 1804 KB Output is partially correct
18 Partially correct 866 ms 1800 KB Output is partially correct
19 Partially correct 851 ms 1756 KB Output is partially correct
20 Partially correct 795 ms 1720 KB Output is partially correct
21 Partially correct 975 ms 1860 KB Output is partially correct
22 Partially correct 840 ms 1776 KB Output is partially correct
23 Partially correct 1483 ms 1744 KB Output is partially correct
24 Correct 10 ms 1816 KB Output is correct
25 Correct 12 ms 1720 KB Output is correct
26 Correct 20 ms 1716 KB Output is correct
27 Correct 13 ms 1684 KB Output is correct
28 Correct 13 ms 1792 KB Output is correct
29 Correct 25 ms 1764 KB Output is correct
30 Correct 42 ms 1752 KB Output is correct