oj.uz

Submission #728308

# Submission time Handle Problem Language Result Execution time Memory
728308 2023-04-22T07:12:52 Z SanguineChameleon Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 71684 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct circle {
	int x, y, r;
};

bool intersect(circle C1, circle C2) {
	return 1LL * (C1.r + C2.r) * (C1.r + C2.r) >= 1LL * (C1.x - C2.x) * (C1.x - C2.x) + 1LL * (C1.y - C2.y) * (C1.y - C2.y); 
}

const int maxn = 3e5 + 20;
circle C[maxn];
int res[maxn];
set<pair<int, int>> S;
map<pair<int, int>, set<int>> groups;
int n;

int floor(int a, int b) {
	return (a / b) - (a % b && (a ^ b) < 0);
}

void build(int len) {
	groups.clear();
	for (auto p: S) {
		int i = p.second;
		int cx = floor(C[i].x, len);
		int cy = floor(C[i].y, len);
		groups[{cx, cy}].insert(i);
	}
}

void just_do_it() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> C[i].x >> C[i].y >> C[i].r;
		S.insert({-C[i].r, i});
	}
	int len = 2e9 + 20;
	while (!S.empty()) {
		int cur = S.begin()->second;
		if (C[cur].r * 2 < len) {
			len = C[cur].r;
			build(len);
		}
		int cx = floor(C[cur].x, len);
		int cy = floor(C[cur].y, len);
		for (int i = -2; i <= 2; i++) {
			for (int j = -2; j <= 2; j++) {
				auto g_it = groups.find({cx + i, cy + j});
				if (g_it == groups.end()) {
					continue;
				}
				auto it = g_it->second.begin();
				while (it != g_it->second.end()) {
					int can = *it;
					if (intersect(C[cur], C[can])) {
						res[can] = cur;
						it = g_it->second.erase(it);
						S.erase({-C[can].r, can});
					}
					else {
						it++;
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << res[i] << " ";
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 6 ms 852 KB Output is correct
22 Correct 17 ms 1364 KB Output is correct
23 Correct 16 ms 1360 KB Output is correct
24 Correct 14 ms 1364 KB Output is correct
25 Correct 13 ms 1360 KB Output is correct
26 Correct 13 ms 1364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 41728 KB Output is correct
2 Correct 755 ms 41908 KB Output is correct
3 Correct 652 ms 41592 KB Output is correct
4 Correct 665 ms 41932 KB Output is correct
5 Correct 627 ms 40268 KB Output is correct
6 Correct 1024 ms 53628 KB Output is correct
7 Correct 686 ms 41616 KB Output is correct
8 Correct 758 ms 43980 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 530 ms 23640 KB Output is correct
3 Correct 2146 ms 71376 KB Output is correct
4 Correct 2125 ms 71412 KB Output is correct
5 Correct 2066 ms 65188 KB Output is correct
6 Correct 846 ms 33516 KB Output is correct
7 Correct 382 ms 17948 KB Output is correct
8 Correct 35 ms 4044 KB Output is correct
9 Correct 2411 ms 70648 KB Output is correct
10 Correct 2080 ms 64464 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1602 ms 70996 KB Output is correct
2 Correct 1187 ms 70404 KB Output is correct
3 Correct 729 ms 51400 KB Output is correct
4 Correct 1241 ms 70840 KB Output is correct
5 Correct 1176 ms 70952 KB Output is correct
6 Correct 678 ms 44548 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 6 ms 852 KB Output is correct
22 Correct 17 ms 1364 KB Output is correct
23 Correct 16 ms 1360 KB Output is correct
24 Correct 14 ms 1364 KB Output is correct
25 Correct 13 ms 1360 KB Output is correct
26 Correct 13 ms 1364 KB Output is correct
27 Correct 11 ms 1492 KB Output is correct
28 Correct 10 ms 1748 KB Output is correct
29 Correct 10 ms 1724 KB Output is correct
30 Correct 29 ms 2624 KB Output is correct
31 Correct 32 ms 2632 KB Output is correct
32 Correct 28 ms 2636 KB Output is correct
33 Correct 185 ms 14888 KB Output is correct
34 Correct 137 ms 14864 KB Output is correct
35 Correct 163 ms 14824 KB Output is correct
36 Correct 489 ms 23740 KB Output is correct
37 Correct 483 ms 23928 KB Output is correct
38 Correct 520 ms 23924 KB Output is correct
39 Correct 951 ms 20916 KB Output is correct
40 Correct 892 ms 21032 KB Output is correct
41 Correct 799 ms 20944 KB Output is correct
42 Correct 296 ms 22864 KB Output is correct
43 Correct 289 ms 23712 KB Output is correct
44 Correct 315 ms 23588 KB Output is correct
45 Correct 283 ms 23568 KB Output is correct
46 Correct 298 ms 23596 KB Output is correct
47 Correct 302 ms 23552 KB Output is correct
48 Correct 298 ms 23572 KB Output is correct
49 Correct 291 ms 23628 KB Output is correct
50 Correct 320 ms 23576 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 5 ms 852 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 6 ms 852 KB Output is correct
22 Correct 17 ms 1364 KB Output is correct
23 Correct 16 ms 1360 KB Output is correct
24 Correct 14 ms 1364 KB Output is correct
25 Correct 13 ms 1360 KB Output is correct
26 Correct 13 ms 1364 KB Output is correct
27 Correct 706 ms 41728 KB Output is correct
28 Correct 755 ms 41908 KB Output is correct
29 Correct 652 ms 41592 KB Output is correct
30 Correct 665 ms 41932 KB Output is correct
31 Correct 627 ms 40268 KB Output is correct
32 Correct 1024 ms 53628 KB Output is correct
33 Correct 686 ms 41616 KB Output is correct
34 Correct 758 ms 43980 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 530 ms 23640 KB Output is correct
37 Correct 2146 ms 71376 KB Output is correct
38 Correct 2125 ms 71412 KB Output is correct
39 Correct 2066 ms 65188 KB Output is correct
40 Correct 846 ms 33516 KB Output is correct
41 Correct 382 ms 17948 KB Output is correct
42 Correct 35 ms 4044 KB Output is correct
43 Correct 2411 ms 70648 KB Output is correct
44 Correct 2080 ms 64464 KB Output is correct
45 Correct 1602 ms 70996 KB Output is correct
46 Correct 1187 ms 70404 KB Output is correct
47 Correct 729 ms 51400 KB Output is correct
48 Correct 1241 ms 70840 KB Output is correct
49 Correct 1176 ms 70952 KB Output is correct
50 Correct 678 ms 44548 KB Output is correct
51 Correct 11 ms 1492 KB Output is correct
52 Correct 10 ms 1748 KB Output is correct
53 Correct 10 ms 1724 KB Output is correct
54 Correct 29 ms 2624 KB Output is correct
55 Correct 32 ms 2632 KB Output is correct
56 Correct 28 ms 2636 KB Output is correct
57 Correct 185 ms 14888 KB Output is correct
58 Correct 137 ms 14864 KB Output is correct
59 Correct 163 ms 14824 KB Output is correct
60 Correct 489 ms 23740 KB Output is correct
61 Correct 483 ms 23928 KB Output is correct
62 Correct 520 ms 23924 KB Output is correct
63 Correct 951 ms 20916 KB Output is correct
64 Correct 892 ms 21032 KB Output is correct
65 Correct 799 ms 20944 KB Output is correct
66 Correct 296 ms 22864 KB Output is correct
67 Correct 289 ms 23712 KB Output is correct
68 Correct 315 ms 23588 KB Output is correct
69 Correct 283 ms 23568 KB Output is correct
70 Correct 298 ms 23596 KB Output is correct
71 Correct 302 ms 23552 KB Output is correct
72 Correct 298 ms 23572 KB Output is correct
73 Correct 291 ms 23628 KB Output is correct
74 Correct 320 ms 23576 KB Output is correct
75 Correct 664 ms 44288 KB Output is correct
76 Correct 728 ms 44076 KB Output is correct
77 Correct 608 ms 44108 KB Output is correct
78 Correct 632 ms 44016 KB Output is correct
79 Correct 943 ms 43896 KB Output is correct
80 Correct 606 ms 44020 KB Output is correct
81 Correct 2051 ms 71456 KB Output is correct
82 Correct 1986 ms 71180 KB Output is correct
83 Correct 2009 ms 71244 KB Output is correct
84 Correct 2163 ms 71684 KB Output is correct
85 Correct 2108 ms 71260 KB Output is correct
86 Correct 2000 ms 71348 KB Output is correct
87 Correct 2399 ms 71248 KB Output is correct
88 Execution timed out 3040 ms 35276 KB Time limit exceeded
89 Halted 0 ms 0 KB -