Submission #724777

#	Time	Username	Problem	Language	Result	Execution time	Memory
724777		Charizard2021	Flight to the Ford (BOI22_communication)	C++17	0 / 100	359 ms	292 KiB

communication

#include<bits/stdc++.h>
#include "communication.h"
using namespace std;
struct Ranges{
    long long left, right;
    Ranges(long long left_, long long right_){
        left = left_;
        right = right_;
    }
    bool inside(long long x){
        return left <= x && x < right;
    }
    long long sizeRange(){
        return right - left;
    }
    Ranges Smaller(long long start, long long end){
        return Ranges(min(right, left + start), min(right, left + start + end));
    }
};
vector<Ranges> splitIntervals(vector<Ranges> v, long long start, long long end) {
    vector<Ranges> r;
    for (Ranges &it : v) {
        if (end > 0 && it.sizeRange() - start > 0){
            r.push_back(it.Smaller(start, end));
        }
        end -= max(0LL, min(end, it.sizeRange() - start));
        start -= min(start, it.sizeRange());
    }
    return r;
}

bool contains(vector<Ranges> v, long long x) {
    for (Ranges &it : v){
        if (it.inside(x)){
            return true;
        }
    }
    return false;
}
struct Node {
    long long end[2] = {0, 0};
    vector<vector<Ranges> > v;
    Node(long long N): v(2) {
        end[1] = N;
        v[1].emplace_back(1, N + 1);
    }
    Node(vector<vector<vector<Ranges> > > &v2): v(2) {
        for (long long g = 0; g < 2; g++){
            for (vector<Ranges> &v : v2[g]){
                add(g, v);
            }
        }
    }
    void add(long long g, Ranges it) {
        end[g] += it.sizeRange();
        v[g].push_back(it);
    }
    void add(long long x, vector<Ranges> &v) {
        for (Ranges &it : v){
            add(x, it);
        }
    }
    vector<vector<vector<Ranges> > > split() {
        vector<vector<vector<Ranges> > > r(2);
        for (long long g = 0; g < 2; g++) {
            long long s1 = (end[g] + g) / 2, s2 = end[g] - s1;
            r[g].push_back(splitIntervals(v[g], 0, s1));
            r[g].push_back(splitIntervals(v[g], s1, s2));
        }
        return r;
    }
    long long size() {
        return end[0] + end[1];
    }
    vector<long long> remaining() {
        vector<long long> r;
        for (long long g = 0; g < 2; g++){
            for (Ranges &it : v[g]){
                for (long long v = it.left; v < it.right; v++){
                    r.push_back(v);
                }
            }
        }
        return r;
    }
};

pair<long long, long long> solve(long long N, long long X) {
    Node v2(N);
    while (v2.size() > 3) {
        vector<vector<vector<Ranges> > > v = v2.split();
        long long b = X != -1 ? send(contains(v[0][0], X) || contains(v[1][0], X)) : receive();
        v[0].erase(v[0].begin() + b);
        swap(v[0][0], v[1][b]);
        v2 = Node(v);
    }
    vector<long long> r = v2.remaining();
    if ((long long) r.size() == 3) {
        long long b1 = 1, b2;
        for (long long i = 0; i < 2 && b1; i++){
            b1 = X != -1 ? send(r[0] == X || r[1] == X) : receive();
            if (!b1){
                b2 = X != -1 ? send(r[0] == X) : receive();
                r.erase(r.begin() + (b1 ? 2 : (b2 ? 1 : 0)));
            }
        }
    }
    return {r[0], r.back()};
}
void encode(int N, int X) {
    solve(N, X);
}
pair<int, int> decode(int N) {
    return solve(N, -1);
}

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