oj.uz

Submission #417992

# Submission time Handle Problem Language Result Execution time Memory
417992 2021-06-04T19:24:21 Z dolphingarlic Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 699084 KB 
#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<tuple<ll, ll, ll>> grids_in_circle[300001];
map<tuple<ll, ll, ll>, unordered_set<int>> circles_in_grid;
vector<pair<ll, int>> remaining;

bool circle_in_grid(int c, ll sx, ll sy, int scale) {
    ll x1 = sx << scale, x2 = (sx + 1) << scale;
    ll 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, y[i] += MX;
        min_grid[i] = 31 - __builtin_clz(2 * r[i]);
        for (int j = min_grid[i]; j <= 30; j++) {
            ll lbx = x[i] >> j, lby = y[i] >> j;
            for (ll dx : {-1, 0, 1}) for (ll dy : {-1, 0, 1})
                if (lbx + dx >= 0 && lby + dy >= 0 && circle_in_grid(i, lbx + dx, lby + dy, j)) {
                    grids_in_circle[i].insert({lbx + dx, lby + dy, j});
                    circles_in_grid[{lbx + dx, lby + dy, j}].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;
}

/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Runtime error 21 ms 28988 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2518 ms 699084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 29132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 412384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Runtime error 21 ms 28988 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Runtime error 21 ms 28988 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -