Submission #1155147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155147		fve5	Circle selection (APIO18_circle_selection)	C++20	0 / 100	3094 ms	79660 KiB

circle_selection

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

typedef long long i64;

struct circle {
    int idx;
    i64 x, y, r;
};

bool operator<(const circle &u, const circle &v) { return make_pair(-u.r, u.idx) < make_pair(-v.r, v.idx); }
bool sect(const circle &u, const circle &v) { return (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) <= (u.r + v.r) * (u.r + v.r); }

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;

    multiset<circle> circles;
    for (int i = 0; i < N; i++) {
        int x, y, r; cin >> x >> y >> r,
        circles.insert(circle{i, x, y, r});
    }

    vector<int> answer(N);

    int step = 1 << 30;
    map<pair<int, int>, vector<multiset<circle>::iterator>> grid;

    auto rebuild = [&]() {
        grid.clear();
        for (auto it = circles.begin(); it != circles.end(); it++)
            grid[{it->x / step, it->y / step}].push_back(it);
    };

    while (!circles.empty()) {
        circle eliminator = *circles.begin(); circles.erase(circles.begin());
        answer[eliminator.idx] = eliminator.idx;
        if (eliminator.r < step) {
            step /= 2;
            rebuild();
        }

        for (int gx = eliminator.x / step - 2; gx <= eliminator.x / step + 2; gx++) {
            for (int gy = eliminator.y / step - 2; gy <= eliminator.y / step + 2; gy++) {
                for (auto it: grid[{gx, gy}]) {
                    if (sect(*it, eliminator)) {
                        answer[it->idx] = eliminator.idx;
                        circles.erase(it);
                    }
                }
            }
        }
    }

    for (auto x: answer)
        cout << x + 1 << ' ';
    cout << '\n';
}

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