제출 #1160989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160989		not_amir	원 고르기 (APIO18_circle_selection)	C++20	49 / 100	3096 ms	22256 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct circle {
    ll x, y, r;
};

bool intersect(circle a, circle b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) <= (a.r + b.r) * (a.r + b.r);
}

constexpr int B = 700;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<circle> c(n);
    for (int i = 0; i < n; i++)
        cin >> c[i].x >> c[i].y >> c[i].r;
    vector<array<ll, 3>> cmp;
    vector ans(n, - 1);
    ll r;
    auto compress = [&](ll nr) {
        r = 2 * nr;
        cmp.clear();
        for (int i = 0; i < n; i++)
            if (ans[i] == -1)
                cmp.push_back({c[i].x / r, c[i].y / r, i});
        sort(cmp.begin(), cmp.end());
    };
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        if (c[a].r == c[b].r)
            return a < b;
        return c[a].r > c[b].r;
    });
    int t = 0;
    for (int i : ord) {
        if (t++ % B == 0)
            compress(c[i].r);
        if (ans[i] >= 0)
            continue;
        ans[i] = i;
        ll cx = c[i].x / r, cy = c[i].y / r;
        for (int x = cx - 1; x <= cx + 1; x++) {
            auto it = lower_bound(cmp.begin(), cmp.end(), array<ll, 3>({x, cy - 1, -1}));
            while (it != cmp.end() && (*it)[0] == x && (*it)[1] <= cy + 1) {
                if (ans[(*it)[2]] == -1 && intersect(c[(*it)[2]], c[i]))
                    ans[(*it)[2]] = i;
                it++;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] + 1 << " ";
}

/*
3
0 0 3
1 2 3
2 2 3
*/

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