Submission #1155160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155160		fve5	Circle selection (APIO18_circle_selection)	C++20	49 / 100	3101 ms	311164 KiB

circle_selection

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

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 = 1 << 30;
    map<i64, vector<multiset<circle>::iterator>> grid;

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

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

        for (i64 gx = eliminator.x / (2 * step) - 2; gx <= eliminator.x / (2 * step) + 2; gx++) {
            for (i64 gy = eliminator.y / (2 * step) - 2; gy <= eliminator.y / (2 * step) + 2; gy++) {
                auto& grid_elems = grid[(gx << 30) | 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: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13