Submission #562013

#	Time	Username	Problem	Language	Result	Execution time	Memory
562013		KoD	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1171 ms	77796 KiB

circle_selection

#include <bits/stdc++.h>

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

constexpr int MAX = 1000000000;
constexpr int LOG = 31;

int main() {
    int N;
    std::cin >> N;
    vector<int> X(N), Y(N), R(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i] >> R[i];
        X[i] += MAX;
    }

    int logR = LOG;
    vector<int> xs = {0};
    vector<vector<int>> pts = {{}};
    for (int i = 0; i < N; ++i) {
        pts[0].push_back(i);
    }
    std::sort(pts[0].begin(), pts[0].end(),
              [&](const int i, const int j) { return Y[i] < Y[j]; });

    vector<int> order(N), ans(N, -1);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(),
              [&](const int i, const int j) { return R[i] != R[j] ? R[i] > R[j] : i < j; });
    for (const int i : order) {
        if (ans[i] != -1) {
            continue;
        }
        while (R[i] <= (1 << (logR - 1))) {
            logR -= 1;
            vector<int> next_xs;
            vector<vector<int>> next_pts;
            for (int i = 0; i < (int)xs.size(); ++i) {
                array<vector<int>, 2> arr;
                for (const int j : pts[i]) {
                    arr[X[j] >> logR & 1].push_back(j);
                }
                for (int k = 0; k < 2; ++k) {
                    if (!arr[k].empty()) {
                        next_xs.push_back(xs[i] * 2 + k);
                        next_pts.push_back(std::move(arr[k]));
                    }
                }
            }
            xs = std::move(next_xs);
            pts = std::move(next_pts);
        }
        ans[i] = i;
        int xi = std::lower_bound(xs.begin(), xs.end(), (X[i] >> logR) - 2) - xs.begin();
        while (xi < (int)xs.size() && xs[xi] <= (X[i] >> logR) + 2) {
            const auto& ys = pts[xi];
            int yi = std::partition_point(ys.begin(), ys.end(),
                                          [&](const int j) { return Y[i] - Y[j] > 2 * R[i]; }) -
                     ys.begin();
            while (yi < (int)ys.size() && Y[ys[yi]] - Y[i] <= 2 * R[i]) {
                const int j = ys[yi];
                if (ans[j] == -1) {
                    const long long dx = X[i] - X[j];
                    const long long dy = Y[i] - Y[j];
                    const long long r = R[i] + R[j];
                    if (dx * dx + dy * dy <= r * r) {
                        ans[j] = i;
                    }
                }
                yi += 1;
            }
            xi += 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] + 1 << " \n"[i + 1 == N];
    }
    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