oj.uz

Submission #536402

# Submission time Handle Problem Language Result Execution time Memory
536402 2022-03-13T07:41:55 Z KoD Towns (IOI15_towns) C++17
100 / 100
 24 ms 908 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 11 ms 372 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 15 ms 368 KB Output is correct
5 Correct 15 ms 368 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 364 KB Output is correct
2 Correct 11 ms 372 KB Output is correct
3 Correct 16 ms 368 KB Output is correct
4 Correct 15 ms 340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 368 KB Output is correct
2 Correct 24 ms 888 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 23 ms 868 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 356 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 20 ms 864 KB Output is correct
3 Correct 17 ms 908 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 368 KB Output is correct
2 Correct 18 ms 872 KB Output is correct
3 Correct 22 ms 868 KB Output is correct