Submission #724779

#	Time	Username	Problem	Language	Result	Execution time	Memory
724779		Charizard2021	Flight to the Ford (BOI22_communication)	C++17	100 / 100	3652 ms	2140 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 s) {
        return Ranges(min(right, left + start), min(right, left + start + s));
    }
};
vector<Ranges> splitIntervals(vector<Ranges> v, long long start, long long s) {
    vector<Ranges> right;
    for(int i = 0; i < v.size(); i++){
        if (s > 0 && v[i].sizeRange() - start > 0){
            right.push_back(v[i].smaller(start, s));
        }
        s -= max(0ll, min(s, v[i].sizeRange() - start));
        start -= min(start, v[i].sizeRange());
    }
    return right;
}

bool contains(vector<Ranges> v, long long x) {
    for(int i = 0; i < v.size(); i++){
        if (v[i].inside(x)){
            return true;
        }
    }
    return false;
}

struct Node {
    long long s[2] = {0, 0};
    vector<vector<Ranges> > v;
    Node(long long N): v(2) {
        s[1] = N;
        v[1].emplace_back(1, N + 1);
    }
    Node(vector<vector<vector<Ranges> > > &cs): v(2) {
        for (int g = 0; g < 2; g++)
            for (vector<Ranges> &v : cs[g])
                add(g, v);
    }
    void add(int g, Ranges it) {
        s[g] += it.sizeRange();
        v[g].push_back(it);
    }
    void add(int g, vector<Ranges> &v) {
        for(int i = 0; i < v.size(); i++){
            add(g, v[i]);
        }
    }
    vector<vector<vector<Ranges> > > split() {
        vector<vector<vector<Ranges> > > right(2);
        for (int g = 0; g < 2; g++) {
            int s1 = (s[g] + g) / 2, s2 = s[g] - s1;
            right[g].push_back(splitIntervals(v[g], 0, s1));
            right[g].push_back(splitIntervals(v[g], s1, s2));
        }
        return right;
    }
    long long size() {
        return s[0] + s[1];
    }
    vector<long long> remaining() {
        vector<long long> right;
        for (int g = 0; g < 2; g++){
            for(int i = 0; i < v[g].size(); i++){
                for (long long v2 = v[g][i].left; v2 < v[g][i].right; v2++){
                    right.push_back(v2);
                }
            }
        }
        return right;
    }
};

std::pair<int, int> solve(int N, int X = -1) {
    Node s(N);
    while (s.size() > 3) {
        vector<vector<vector<Ranges> > > v = s.split();
        int 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]);
        s = Node(v);
    }
    vector<long long> right = s.remaining();
    if ((int) right.size() == 3) {
        int b1 = 1, b2;
        for (int i = 0; i < 2 && b1; i++)
        b1 = X != -1 ? send(right[0] == X || right[1] == X) : receive();
        if (!b1)
        b2 = X != -1 ? send(right[0] == X) : receive();
        right.erase(right.begin() + (b1 ? 2 : (b2 ? 1 : 0)));
    }
    return make_pair(right[0], right.back());
}
void encode(int N, int X) {
    solve(N, X);
}
std::pair<int, int> decode(int N) {
    return solve(N);
}

Compilation message (stderr)

communication.cpp: In function 'std::vector<Ranges> splitIntervals(std::vector<Ranges>, long long int, long long int)':
communication.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
communication.cpp: In function 'bool contains(std::vector<Ranges>, long long int)':
communication.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
communication.cpp: In member function 'void Node::add(int, std::vector<Ranges>&)':
communication.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i = 0; i < v.size(); i++){
      |                        ~~^~~~~~~~~~
communication.cpp: In member function 'std::vector<long long int> Node::remaining()':
communication.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ranges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(int i = 0; i < v[g].size(); i++){
      |                            ~~^~~~~~~~~~~~~

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