Submission #393580

#	Time	Username	Problem	Language	Result	Execution time	Memory
393580		KoD	Circle selection (APIO18_circle_selection)	C++17	19 / 100	1252 ms	53500 KiB

circle_selection

#include <bits/stdc++.h>

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

using ll = long long;

constexpr ll sq(const ll x) {
    return x * x;
}

int main() {
    int N;
    std::cin >> N;
    Vec<ll> X(N), Y(N), R(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i] >> R[i];
    }
    Vec<int> order(N);
    std::iota(order.begin(), order.end(), 0);
    std::stable_sort(order.begin(), order.end(), [&](const int i, const int j) {
        return R[i] > R[j];
    });
    Vec<int> ans(N, -1);
    if (N <= 5000) {
        for (const auto x: order) {
            if (ans[x] == -1) {
                ans[x] = x;
                for (int i = 0; i < N; ++i) {
                    if (ans[i] == -1 and sq(X[i] - X[x]) + sq(Y[i] - Y[x]) <= sq(R[i] + R[x])) {
                        ans[i] = x;
                    }
                }
            }    
        }
    }
    else {
        std::set<std::pair<ll, int>> set;
        for (int i = 0; i < N; ++i) {
            set.emplace(X[i] - R[i], i);
            set.emplace(X[i] + R[i], i);
        }
        for (const auto x: order) {
            if (ans[x] == -1) {
                ans[x] = x;
                while (true) {
                    auto itr = set.lower_bound(std::make_pair(X[x] - R[x], 0));
                    if (itr == set.end() or itr -> first > X[x] + R[x]) {
                        break;
                    }
                    const auto i = itr -> second;
                    ans[i] = x;
                    set.erase(std::make_pair(X[i] - R[i], i));
                    set.erase(std::make_pair(X[i] + R[i], i));
                }
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] + 1 << " \n"[i + 1 == N];
    }
}

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