Submission #1155155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155155		fve5	Circle selection (APIO18_circle_selection)	C++20	0 / 100	3087 ms	25040 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 + (i64)1e9, y + (i64)1e9, r});
    }

    vector<int> answer(N);

    i64 step = 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 + 1), it->y >> (step + 1)}].push_back(it);
    };

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

        for (int gx = (eliminator.x >> (step + 1)) - 2; gx <= (eliminator.x >> (step + 1)) + 2; gx++) {
            for (int gy = (eliminator.y >> (step + 1)) - 2; gy <= (eliminator.y >> (step + 1)) + 2; gy++) {
                auto& grid_elems = grid[{gx, gy}];
                for (int i = 0; i < grid_elems.size(); i++) {
                    if (sect(*grid_elems[i], eliminator)) {
                        answer[grid_elems[i]->idx] = eliminator.idx;
                        circles.erase(grid_elems[i]);
                        swap(grid_elems[i], grid_elems.back());
                        grid_elems.pop_back();
                        i--;
                    }
                }
            }
        }
    }

    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