Submission #417990

#	Time	Username	Problem	Language	Result	Execution time	Memory
417990		dolphingarlic	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3115 ms	658528 KiB

circle_selection

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

const ll MX = 1e9;

int ord[300001], ans[300001];
ll x[300001], y[300001], r[300001], min_grid[300001];
set<pair<ll, ll>> grids_in_circle[300001];
map<pair<ll, ll>, unordered_set<int>> circles_in_grid;
vector<pair<ll, int>> remaining;

bool circle_in_grid(int c, int sx, int sy, int scale) {
    int x1 = sx << scale, x2 = (sx + 1) << scale;
    int y1 = sy << scale, y2 = (sy + 1) << scale;
    // Case 1: The circle is inside the grid square
    if (x1 <= x[c] && x[c] <= x2 && y1 <= y[c] && y[c] <= y2) return true;
    // Case 2: The circle is outside the grid square
    if (min({
        hypot(x1 - x[c], y1 - y[c]),
        hypot(x1 - x[c], y2 - y[c]),
        hypot(x2 - x[c], y1 - y[c]),
        hypot(x2 - x[c], y2 - y[c])
    }) <= r[c]) return true;
    return false;
}

bool circles_intersect(int c1, int c2) {
    return hypot(x[c1] - x[c2], y[c1] - y[c2]) <= r[c1] + r[c2];
}

void remove_circle(int c) {
    for (auto g : grids_in_circle[c])
        circles_in_grid[g].erase(c);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> r[i];
        x[i] += MX + 1, y[i] += MX + 1;
        min_grid[i] = 31 - __builtin_clz(2 * r[i]);
        for (int j = min_grid[i]; j <= 30; j++) {
            int lbx = x[i] >> j, lby = y[i] >> j;
            for (int dx : {-1, 0, 1}) for (int dy : {-1, 0, 1})
                if (circle_in_grid(i, lbx + dx, lby + dy, j)) {
                    grids_in_circle[i].insert({lbx + dx, lby + dy});
                    circles_in_grid[{lbx + dx, lby + dy}].insert(i);
                }
        }
    }
    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [](int A, int B) {
        if (r[A] == r[B]) return A < B;
        return r[A] > r[B];
    });
    for (int i = 1; i <= n; i++) {
        int curr = ord[i];
        if (ans[curr]) continue;
        for (auto g : grids_in_circle[curr]) for (int c : circles_in_grid[g]) {
            if (circles_intersect(curr, c)) {
                ans[c] = curr;
                remove_circle(c);
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    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