oj.uz

Submission #1087252

# Submission time Handle Problem Language Result Execution time Memory
1087252 2024-09-12T11:30:35 Z TrungNotChung Circle selection (APIO18_circle_selection) C++11
64 / 100
 3000 ms 49264 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define task "main"

using namespace std;
const int N = (int)3e5 + 10; 

struct Circle {
    int x, y, r, i;
    Circle(int _x = 0, int _y = 0, int _r = 0, int _i = 0) {
        x = _x, y = _y, r = _r, i = _i;
    }
} circles[N];

int n;
int res[N];
 
bool cmp(const Circle &a, const Circle &b){
    if (a.r == b.r) return a.i < b.i;
    return a.r > b.r;
}

bool intersect(const Circle &a, const Circle &b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y) <= 1LL * (a.r + b.r) * (a.r + b.r);
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> circles[i].x >> circles[i].y >> circles[i].r;
        circles[i].i = i;
    }
    sort (circles, circles + n, cmp);

    memset(res, -1, sizeof res);
    for (int lg = 30; lg >= 0; --lg) {
        int r = (1 << lg);
        map<pii, vector<int> > grid;
        for (int i = 0; i < n; ++i) {
            if (res[circles[i].i] == -1) {
                grid[pii(circles[i].x / r, circles[i].y / r)].push_back(i);
            }
        }
        for (int i = 0; i < n; ++i) {
            Circle &cur = circles[i];
            if (cur.r < r / 2) break;
            if (res[cur.i] != -1 || cur.r > r) continue;
            for(int x = cur.x / r - 2; x <= cur.x / r + 2; ++x) {
                for(int y = cur.y / r - 2; y <= cur.y / r + 2; ++y) {
                    if (grid.find(pii(x, y)) == grid.end()) continue;
                    for(int c : grid[pii(x,y)]) {
                        if(res[circles[c].i] == -1 && intersect(circles[c], cur)) {
                            res[circles[c].i] = cur.i;
                        }
                    }
                }
            }
        }
    }

    for(int i = 0; i < n; i++) cout << res[i] + 1 << ' ';
}
 
int main() {
#ifdef LOCAL
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 2 ms 6176 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6184 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 3 ms 6236 KB Output is correct
12 Correct 3 ms 6236 KB Output is correct
13 Correct 2 ms 6180 KB Output is correct
14 Correct 2 ms 6236 KB Output is correct
15 Correct 3 ms 6236 KB Output is correct
16 Correct 3 ms 6232 KB Output is correct
17 Correct 3 ms 6236 KB Output is correct
18 Correct 3 ms 6232 KB Output is correct
19 Correct 4 ms 6492 KB Output is correct
20 Correct 5 ms 6464 KB Output is correct
21 Correct 4 ms 6492 KB Output is correct
22 Correct 20 ms 7064 KB Output is correct
23 Correct 21 ms 7036 KB Output is correct
24 Correct 20 ms 7000 KB Output is correct
25 Correct 22 ms 7004 KB Output is correct
26 Correct 21 ms 7000 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 12916 KB Output is correct
2 Correct 143 ms 14156 KB Output is correct
3 Correct 141 ms 13536 KB Output is correct
4 Correct 136 ms 12240 KB Output is correct
5 Correct 333 ms 13596 KB Output is correct
6 Correct 877 ms 23704 KB Output is correct
7 Correct 379 ms 14384 KB Output is correct
8 Correct 530 ms 16508 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB Output is correct
2 Correct 511 ms 19472 KB Output is correct
3 Correct 2318 ms 45468 KB Output is correct
4 Correct 2354 ms 49264 KB Output is correct
5 Correct 1687 ms 43868 KB Output is correct
6 Correct 669 ms 24640 KB Output is correct
7 Correct 307 ms 15996 KB Output is correct
8 Correct 56 ms 8284 KB Output is correct
9 Correct 2113 ms 48376 KB Output is correct
10 Correct 1418 ms 40972 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2561 ms 47536 KB Output is correct
2 Execution timed out 3019 ms 46600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 2 ms 6176 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6184 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 3 ms 6236 KB Output is correct
12 Correct 3 ms 6236 KB Output is correct
13 Correct 2 ms 6180 KB Output is correct
14 Correct 2 ms 6236 KB Output is correct
15 Correct 3 ms 6236 KB Output is correct
16 Correct 3 ms 6232 KB Output is correct
17 Correct 3 ms 6236 KB Output is correct
18 Correct 3 ms 6232 KB Output is correct
19 Correct 4 ms 6492 KB Output is correct
20 Correct 5 ms 6464 KB Output is correct
21 Correct 4 ms 6492 KB Output is correct
22 Correct 20 ms 7064 KB Output is correct
23 Correct 21 ms 7036 KB Output is correct
24 Correct 20 ms 7000 KB Output is correct
25 Correct 22 ms 7004 KB Output is correct
26 Correct 21 ms 7000 KB Output is correct
27 Correct 8 ms 6748 KB Output is correct
28 Correct 7 ms 6680 KB Output is correct
29 Correct 6 ms 6740 KB Output is correct
30 Correct 42 ms 7604 KB Output is correct
31 Correct 45 ms 7540 KB Output is correct
32 Correct 42 ms 7756 KB Output is correct
33 Correct 46 ms 10056 KB Output is correct
34 Correct 51 ms 9988 KB Output is correct
35 Correct 51 ms 10428 KB Output is correct
36 Correct 586 ms 20384 KB Output is correct
37 Correct 589 ms 20536 KB Output is correct
38 Correct 544 ms 20544 KB Output is correct
39 Correct 313 ms 14192 KB Output is correct
40 Correct 305 ms 14000 KB Output is correct
41 Correct 305 ms 14068 KB Output is correct
42 Correct 238 ms 15084 KB Output is correct
43 Correct 479 ms 20128 KB Output is correct
44 Correct 473 ms 20380 KB Output is correct
45 Correct 490 ms 20060 KB Output is correct
46 Correct 495 ms 19824 KB Output is correct
47 Correct 482 ms 19796 KB Output is correct
48 Correct 483 ms 20052 KB Output is correct
49 Correct 477 ms 19960 KB Output is correct
50 Correct 482 ms 19812 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 2 ms 6176 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 2 ms 6184 KB Output is correct
10 Correct 2 ms 6236 KB Output is correct
11 Correct 3 ms 6236 KB Output is correct
12 Correct 3 ms 6236 KB Output is correct
13 Correct 2 ms 6180 KB Output is correct
14 Correct 2 ms 6236 KB Output is correct
15 Correct 3 ms 6236 KB Output is correct
16 Correct 3 ms 6232 KB Output is correct
17 Correct 3 ms 6236 KB Output is correct
18 Correct 3 ms 6232 KB Output is correct
19 Correct 4 ms 6492 KB Output is correct
20 Correct 5 ms 6464 KB Output is correct
21 Correct 4 ms 6492 KB Output is correct
22 Correct 20 ms 7064 KB Output is correct
23 Correct 21 ms 7036 KB Output is correct
24 Correct 20 ms 7000 KB Output is correct
25 Correct 22 ms 7004 KB Output is correct
26 Correct 21 ms 7000 KB Output is correct
27 Correct 142 ms 12916 KB Output is correct
28 Correct 143 ms 14156 KB Output is correct
29 Correct 141 ms 13536 KB Output is correct
30 Correct 136 ms 12240 KB Output is correct
31 Correct 333 ms 13596 KB Output is correct
32 Correct 877 ms 23704 KB Output is correct
33 Correct 379 ms 14384 KB Output is correct
34 Correct 530 ms 16508 KB Output is correct
35 Correct 3 ms 6236 KB Output is correct
36 Correct 511 ms 19472 KB Output is correct
37 Correct 2318 ms 45468 KB Output is correct
38 Correct 2354 ms 49264 KB Output is correct
39 Correct 1687 ms 43868 KB Output is correct
40 Correct 669 ms 24640 KB Output is correct
41 Correct 307 ms 15996 KB Output is correct
42 Correct 56 ms 8284 KB Output is correct
43 Correct 2113 ms 48376 KB Output is correct
44 Correct 1418 ms 40972 KB Output is correct
45 Correct 2561 ms 47536 KB Output is correct
46 Execution timed out 3019 ms 46600 KB Time limit exceeded
47 Halted 0 ms 0 KB -