Submission #1179396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179396		Iskachun	Flight to the Ford (BOI22_communication)	C++20	100 / 100	1092 ms	3624 KiB

communication

#include<vector>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<cstdarg>
#include<cassert>
using namespace std;

#include "communication.h"
struct state {
    int one = 0, two = 0;
    vector<pair<int,int>> a, b;
};
void split (state &s, state &l, state &r) {
    auto &[one, two, a, b] = s;
    int left1 = (one + 1) / 2, left2 = two / 2;
    for (auto [left, right] : a) {
        if (right - left + 1 <= left1) l.a.push_back({left, right});
        else if (left1 <= 0) r.a.push_back({left, right});
        else l.a.push_back({left, left + left1 - 1}), r.a.push_back({left + left1, right});
        left1 -= right - left + 1;
    }
    r.b = l.a, l.b = r.a;
    for (auto [left, right] : b) {
        if (right - left + 1 <= left2) l.a.push_back({left, right});
        else if (left2 <= 0) r.a.push_back({left, right});
        else l.a.push_back({left, left + left2 - 1}), r.a.push_back({left + left2, right});
        left2 -= right - left + 1;
    }
}
pair<int,int> div (state s, int x, int flag) {
    auto &[one, two, a, b] = s;
    for (auto [left, right] : a) one += right - left + 1;
    for (auto [left, right] : b) two += right - left + 1;
    if (one <= 2 and two <= 1) {
        vector<int> v;
        for (auto [left, right] : a) {
            for (int i = left; i <= right; i++) v.push_back(i);
        }
        while (v.size() < 2) v.push_back(1 - flag);
        for (auto [left, right] : b) {
            for (int i = left; i <= right; i++) v.push_back(i);
        }
        while (v.size() < 3) v.push_back(1 - flag);
        if (flag) {
            if (x == v[0]) send(1), send(1);
            else if (x == v[1]) send(1), send(0);
            else send(0), send(0);
            return {0, 0};
        } else {
            int ans = receive() * 2 + receive();
            if (ans == 2 or ans == 3) return {v[0], v[1]};
            else if (ans == 1) return {v[0], v[2]};
            else return {v[1], v[2]};
        }
    }
    state left, right;
    split(s, left, right);
    int signal = 1;
    for (auto [l, r] : left.a) {
        if (l <= x and x <= r) {signal = 0; break;}
    }
    int ans = 0;
    if (flag) ans = send(signal);
    else ans = receive();
    if (ans == 0) return div(left, x, flag);
    else return div(right, x, flag);
}
void encode (int n, int x) {
    state s;
    s.a.push_back({1, n});
    div(s, x, 1);
}
pair<int,int> decode (int n) {
    state s;
    s.a.push_back({1, n});
    return div(s, 0, 0);
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85