oj.uz

Submission #1109719

# Submission time Handle Problem Language Result Execution time Memory
1109719 2024-11-07T11:14:51 Z fve5 Flight to the Ford (BOI22_communication) C++17
100 / 100
 7494 ms 3364 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;
    }
};

constexpr int MAXN = 1e9;

void encode(int N, int X) {
    X--;
    
    Set T = {{{0, MAXN}}};
    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));
    sort(left.begin(), left.end());

    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 = {{{0, MAXN}}};
    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));
    sort(left.begin(), left.end());

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

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 2896 KB Output is correct
2 Correct 291 ms 2700 KB Output is correct
3 Correct 383 ms 2708 KB Output is correct
4 Correct 200 ms 2724 KB Output is correct
5 Correct 303 ms 2704 KB Output is correct
6 Correct 736 ms 2896 KB Output is correct
7 Correct 1540 ms 2716 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1733 ms 2724 KB Output is correct
2 Correct 858 ms 2712 KB Output is correct
3 Correct 1040 ms 2716 KB Output is correct
4 Correct 1826 ms 2704 KB Output is correct
5 Correct 1599 ms 2700 KB Output is correct
6 Correct 1271 ms 2712 KB Output is correct
7 Correct 4804 ms 2824 KB Output is correct
8 Correct 7474 ms 2968 KB Output is correct
9 Correct 6634 ms 2868 KB Output is correct
10 Correct 6707 ms 2980 KB Output is correct
11 Correct 6838 ms 2888 KB Output is correct
12 Correct 6778 ms 3364 KB Output is correct
13 Correct 6749 ms 3044 KB Output is correct
14 Correct 6727 ms 2872 KB Output is correct
15 Correct 3507 ms 2884 KB Output is correct
16 Correct 7494 ms 2804 KB Output is correct
17 Correct 1797 ms 2792 KB Output is correct
18 Correct 1765 ms 2896 KB Output is correct
19 Correct 1846 ms 2800 KB Output is correct
20 Correct 1833 ms 2880 KB Output is correct
21 Correct 1864 ms 2844 KB Output is correct
22 Correct 1897 ms 2788 KB Output is correct
23 Correct 3109 ms 2912 KB Output is correct
24 Correct 198 ms 2708 KB Output is correct
25 Correct 266 ms 2708 KB Output is correct
26 Correct 395 ms 2712 KB Output is correct
27 Correct 198 ms 2716 KB Output is correct
28 Correct 285 ms 2708 KB Output is correct
29 Correct 783 ms 2788 KB Output is correct
30 Correct 1591 ms 2704 KB Output is correct