제출 #561991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561991		KoD	원 고르기 (APIO18_circle_selection)	C++17	0 / 100	479 ms	29040 KiB

circle_selection

#include <bits/stdc++.h>

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

constexpr int LOG = 30;

int dedup(vector<int>& vec) {
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    return (int)vec.size();
}

template <class T>
int lowb(const vector<T>& vec, const T& x) {
    return std::lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

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];
    }

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

    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<pair<int, int>>> next_pts;
            for (int i = 0; i < (int)xs.size(); ++i) {
                array<vector<pair<int, int>>, 2> arr;
                for (const auto& [y, j] : pts[i]) {
                    arr[y >> logR & 1].emplace_back(y, 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);
        }
        for (int xi = lowb(xs, (X[i] >> logR) - 2);
             xi < (int)xs.size() && xs[xi] <= (X[i] >> logR) + 2; ++xi) {
            for (int yi = lowb(pts[xi], pair(Y[i] - 2 * R[i], 0));
                 yi < (int)pts[xi].size() && pts[xi][yi].first - 2 * R[i] <= Y[i]; ++yi) {
                const int j = pts[xi][yi].second;
                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;
                    }
                }
            }
        }
        ans[i] = i;
    }
    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] + 1 << " \n"[i + 1 == N];
    }
    return 0;
}

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