Submission #400424

#	Time	Username	Problem	Language	Result	Execution time	Memory
400424		KoD	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1114 ms	85468 KiB

circle_selection

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept {
            return itr != other.itr;
        }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept
        : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr u64 ceil_log2(const u64 x) {
    u64 e = 0;
    while (((u64)1 << e) < x) ++e;
    return e;
}

template <class T> using Vec = std::vector<T>;

constexpr i64 MAX = 1000000000;

constexpr i64 square(const i64 x) { return x * x; }

void APIO18_circle_selection_main() {
    usize N;
    std::cin >> N;
    Vec<i64> X(N), Y(N), R(N);
    for (const auto i : rep(0, N)) {
        std::cin >> X[i] >> Y[i] >> R[i];
        X[i] += MAX;
        Y[i] += MAX;
    }
    const auto intersect = [&](const usize i, const usize j) {
        return square(X[i] - X[j]) + square(Y[i] - Y[j]) <= square(R[i] + R[j]);
    };
    i64 G = (i64)1 << ceil_log2(2 * MAX);
    Vec<i64> unit;
    unit.push_back(0);
    Vec<usize> order(N);
    std::iota(order.begin(), order.end(), (usize)0);
    std::sort(order.begin(), order.end(),
              [&](const usize i, const usize j) { return Y[i] < Y[j]; });
    Vec<Vec<usize>> group;
    group.push_back(order);
    std::sort(order.begin(), order.end(), [&](const usize i, const usize j) {
        return R[i] > R[j] or (R[i] == R[j] and i < j);
    });
    Vec<usize> ans(N);
    std::iota(ans.begin(), ans.end(), (usize)0);
    Vec<bool> done(N);
    for (const auto center : order) {
        if (done[center]) {
            continue;
        }
        done[center] = true;
        while (G / 2 >= R[center]) {
            G /= 2;
            Vec<i64> new_unit;
            Vec<Vec<usize>> new_group;
            for (const auto i : rep(0, unit.size())) {
                const auto to_left = 2 * unit[i];
                const auto itr = std::stable_partition(
                    group[i].begin(), group[i].end(),
                    [&](const usize i) { return X[i] / G == to_left; });
                if (itr != group[i].begin()) {
                    new_unit.push_back(to_left);
                    new_group.emplace_back(group[i].begin(), itr);
                }
                if (itr != group[i].end()) {
                    new_unit.push_back(to_left + 1);
                    new_group.emplace_back(itr, group[i].end());
                }
            }
            unit = std::move(new_unit);
            group = std::move(new_group);
        }
        const auto X_c = X[center] / G;
        const isize X_i =
            std::lower_bound(unit.begin(), unit.end(), X_c) - unit.begin();
        for (isize di = -2; di <= 2; ++di) {
            const auto i = X_i + di;
            if (i < 0 or i >= (isize)unit.size() or
                std::abs(unit[i] - X_c) > 2) {
                continue;
            }
            auto itr = std::partition_point(
                group[i].begin(), group[i].end(), [&](const usize k) {
                    return Y[k] + 2 * R[center] < Y[center];
                });
            while (itr != group[i].end()) {
                const auto k = *itr;
                if (Y[k] - 2 * R[center] > Y[center]) {
                    break;
                }
                if (!done[k] and intersect(center, k)) {
                    ans[k] = center;
                    done[k] = true;
                }
                ++itr;
            }
        }
    }
    for (const auto x : ans) {
        std::cout << x + 1 << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    APIO18_circle_selection_main();
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13