oj.uz

Submission #1109720

# Submission time Handle Problem Language Result Execution time Memory
1109720 2024-11-07T11:22:00 Z fve5 Flight to the Ford (BOI22_communication) C++17
100 / 100
 7518 ms 3264 KB 
#include <bits/stdc++.h>
#include "communication.h"
using namespace std;

struct Range {
    int l, r;

    int size() const { return r - l; }

    pair<Range, Range> split(int take) const { return {{l, l + take}, {l + take, r}}; }
};

struct Set {
    vector<Range> ranges;

    bool has(int x) const {
        return any_of(ranges.begin(), ranges.end(), [&](const Range &r) { return r.l <= x && x < r.r; });
    }

    int size() const {
        int ans = 0;
        for (auto range: ranges)
            ans += range.size();
        return ans;
    }

    pair<Set, Set> split(bool extra_left) const {
        int size_left = (size() + extra_left) / 2;

        Set l, r;
        for (auto &range: ranges) {
            if (size_left == 0) {
                r.ranges.push_back(range);
            } else if (range.size() <= size_left) {
                l.ranges.push_back(range);
                size_left -= range.size();
            } else {
                auto [left, right] = range.split(size_left);
                l.ranges.push_back(left);
                r.ranges.push_back(right);
                size_left -= left.size();
            }
        }

        return {l, r};
    }

    Set join(const Set &o) const {
        Set ans = o;
        copy(ranges.begin(), ranges.end(), back_inserter(ans.ranges));
        return ans;
    }

    vector<int> enumerate() const {
        vector<int> ans;
        for (auto [l, r]: ranges)
            for (int i = l; i < r; i++)
                ans.push_back(i);
        return ans;
    }
};

void encode(int N, int X) {    
    Set T = {{{1, N + 1}}};
    Set F = {{}};

    while (T.size() + F.size() > 3) {
        auto [I_T, D_T] = T.split(true);
        auto [I_F, D_F] = F.split(false);

        bool recv = send(I_T.has(X) || I_F.has(X));
        if (recv) {
            T = I_T.join(I_F);
            F = D_T;
        } else {
            T = D_T.join(D_F);
            F = I_T;
        }
    }

    vector<int> T_left = T.enumerate();
    vector<int> F_left = F.enumerate();

    vector<int> left;
    copy(T_left.begin(), T_left.end(), back_inserter(left));
    copy(F_left.begin(), F_left.end(), back_inserter(left));

    int last = find(left.begin(), left.end(), X) - left.begin();

    switch (last) {
    case 0: send(0); send(0); send(0); send(0); break;
    case 1: send(0); send(1); send(1); send(0); break;
    case 2: send(1); send(0); send(0); send(1); break;
    }
}

pair<int, int> ending_guesses(vector<int> packet) {
    int val = packet[0] | 2 * packet[1] | 4 * packet[2] | 8 * packet[3];
    switch (val) {
        case  0: return {0, 2};
        case  1: return {0, 2};
        case  2: return {0, 1};
        case  3: return {1, 2};
        case  4: return {0, 1};
        case  5: return {0, 0};
        case  6: return {1, 1};
        case  7: return {1, 1};
        case  8: return {0, 2};
        case  9: return {0, 2};
        case 10: return {0, 0};
        case 11: return {2, 2};
        case 12: return {1, 2};
        case 13: return {2, 2};
        case 14: return {1, 1};
        case 15: return {1, 1};
    }
}

pair<int, int> decode(int N) {
    Set T = {{{1, N + 1}}};
    Set F = {{}};

    while (T.size() + F.size() > 3) {
        auto [I_T, D_T] = T.split(true);
        auto [I_F, D_F] = F.split(false);

        if (receive()) {
            T = I_T.join(I_F);
            F = D_T;
        } else {
            T = D_T.join(D_F);
            F = I_T;
        }
    }

    vector<int> T_left = T.enumerate();
    vector<int> F_left = F.enumerate();

    vector<int> left;
    copy(T_left.begin(), T_left.end(), back_inserter(left));
    copy(F_left.begin(), F_left.end(), back_inserter(left));

    auto [t1, t2] = ending_guesses({receive(), receive(), receive(), receive()});
    return {left[t1], left[t2]};
}

Compilation message

communication.cpp: In function 'std::pair<int, int> ending_guesses(std::vector<int>)':
communication.cpp:117:1: warning: control reaches end of non-void function [-Wreturn-type]
  117 | }
      | ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2736 KB Output is correct
2 Correct 23 ms 2944 KB Output is correct
3 Correct 30 ms 2736 KB Output is correct
4 Correct 17 ms 2748 KB Output is correct
5 Correct 19 ms 2736 KB Output is correct
6 Correct 44 ms 2912 KB Output is correct
7 Correct 77 ms 2708 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 2720 KB Output is correct
2 Correct 850 ms 2708 KB Output is correct
3 Correct 1018 ms 2712 KB Output is correct
4 Correct 1815 ms 3064 KB Output is correct
5 Correct 1566 ms 2884 KB Output is correct
6 Correct 1264 ms 2712 KB Output is correct
7 Correct 4693 ms 2808 KB Output is correct
8 Correct 7518 ms 3068 KB Output is correct
9 Correct 6628 ms 3152 KB Output is correct
10 Correct 6656 ms 3068 KB Output is correct
11 Correct 6567 ms 3060 KB Output is correct
12 Correct 6701 ms 2976 KB Output is correct
13 Correct 6760 ms 2876 KB Output is correct
14 Correct 6796 ms 3128 KB Output is correct
15 Correct 3504 ms 3072 KB Output is correct
16 Correct 7414 ms 2900 KB Output is correct
17 Correct 1854 ms 2884 KB Output is correct
18 Correct 1833 ms 2876 KB Output is correct
19 Correct 1828 ms 3076 KB Output is correct
20 Correct 1890 ms 2792 KB Output is correct
21 Correct 1864 ms 2888 KB Output is correct
22 Correct 1823 ms 2796 KB Output is correct
23 Correct 2976 ms 3264 KB Output is correct
24 Correct 18 ms 2716 KB Output is correct
25 Correct 21 ms 2720 KB Output is correct
26 Correct 22 ms 2728 KB Output is correct
27 Correct 17 ms 2716 KB Output is correct
28 Correct 22 ms 2776 KB Output is correct
29 Correct 43 ms 2880 KB Output is correct
30 Correct 102 ms 2708 KB Output is correct