Submission #536402

#	Time	Username	Problem	Language	Result	Execution time	Memory
536402		KoD	Towns (IOI15_towns)	C++17	100 / 100	24 ms	908 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#include <cmath>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

template <class F> bool majority(const int n, const F& f) {
    vector<int> list, bucket;
    for (int x = 0; x < n; ++x) {
        if (list.empty() || !f(list.back(), x)) {
            list.push_back(x);
            if (!bucket.empty()) {
                list.push_back(bucket.back());
                bucket.pop_back();
            }
        }
        else {
            bucket.push_back(x);
        }
    }
    const auto T = list.back();
    while (!list.empty()) {
        if (f(list.back(), T)) {
            if (list.size() == 1) {
                bucket.push_back(list.back());
                list.pop_back();
            }
            else {
                list.pop_back();
                list.pop_back();
            }
        }
        else {
            if (bucket.empty()) {
                return false;
            }
            list.pop_back();
            bucket.pop_back();
        }
    }
    return !bucket.empty();
}

int hubDistance(int N, int) {
    std::map<pair<int, int>, int> memo;
    const auto dist = [&](const int i, const int j) {
        assert(0 <= i and i < N);
        assert(0 <= j and j < N);
        if (i == j) {
            return 0;
        }
        const auto p = std::minmax(i, j);
        if (const auto itr = memo.find(p); itr != memo.end()) {
            return itr->second;
        }
        return memo[p] = getDistance(i, j);
    };

    int X = 0;
    for (int i = 1; i < N; ++i) {
        if (dist(0, X) < dist(0, i)) {
            X = i;
        }
    }
    int Y = 0;
    for (int i = 1; i < N; ++i) {
        if (dist(X, Y) < dist(X, i)) {
            Y = i;
        }
    }

    const int len = dist(0, X);
    const int diameter = dist(X, Y);

    const auto get_pos = [&](const int i) {
        const int l = dist(0, i);
        const int r = dist(X, i);
        const int d = (l + r - len) / 2;
        return r - d;
    };

    std::map<int, vector<int>> group;
    int min = 1000000000;
    for (int i = 0; i < N; ++i) {
        const int pos = get_pos(i);
        min = std::min(min, std::max(pos, diameter - pos));    
        group[pos].push_back(i);
    }

    int left = 0;
    vector<char> cand(N);
    for (const auto& [pos, list] : group) {
        const int n = (int)list.size();
        if (std::max(left, N - n - left) <= N / 2 and min == std::max(pos, diameter - pos)) {
            for (const int i : list) {
                cand[i] = true;
            }
        }
        left += n;
    }

    if (std::all_of(cand.begin(), cand.end(), [&](const char c) { return !c; })) {
        return -min;
    }
    return majority(N, [&](const int i, const int j) {
        const int pos = get_pos(i);
        return cand[i] and cand[j] and pos == get_pos(j) and dist(X, i) + dist(X, j) - dist(i, j) > 2 * pos;
    }) ? -min : min;
}

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 39 / 39