oj.uz

Submission #728328

# Submission time Handle Problem Language Result Execution time Memory
728328 2023-04-22T07:35:59 Z SanguineChameleon Circle selection (APIO18_circle_selection) C++17
100 / 100
 1320 ms 60752 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<int, vector<pair<int, 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].emplace_back(cy, i);
	}
	for (auto &p: groups) {
		sort(p.second.begin(), p.second.end());
	}
}
 
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 = -1;
	while (!S.empty()) {
		int cur = S.begin()->second;
		if (len == -1 || 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++) {
			auto g_it = groups.find({cx + i});
			if (g_it == groups.end()) {
				continue;
			}
			auto it = lower_bound(g_it->second.begin(), g_it->second.end(), make_pair(cy - 2, -1));
			while (it != g_it->second.end()) {
				if (it->first > cy + 2) {
					break;
				}
				int can = it->second;
				if (!res[can] && intersect(C[cur], C[can])) {
					res[can] = cur;
					S.erase({-C[can].r, can});
				}
				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 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 332 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 320 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 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 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 7 ms 856 KB Output is correct
22 Correct 12 ms 1092 KB Output is correct
23 Correct 9 ms 844 KB Output is correct
24 Correct 8 ms 1104 KB Output is correct
25 Correct 10 ms 1244 KB Output is correct
26 Correct 8 ms 1112 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 22312 KB Output is correct
2 Correct 482 ms 22444 KB Output is correct
3 Correct 508 ms 24356 KB Output is correct
4 Correct 465 ms 23760 KB Output is correct
5 Correct 597 ms 26280 KB Output is correct
6 Correct 1085 ms 38844 KB Output is correct
7 Correct 673 ms 27996 KB Output is correct
8 Correct 732 ms 30088 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 308 ms 9712 KB Output is correct
3 Correct 1174 ms 27988 KB Output is correct
4 Correct 1120 ms 28184 KB Output is correct
5 Correct 944 ms 24732 KB Output is correct
6 Correct 382 ms 14120 KB Output is correct
7 Correct 160 ms 8112 KB Output is correct
8 Correct 24 ms 2612 KB Output is correct
9 Correct 1124 ms 26932 KB Output is correct
10 Correct 1006 ms 24556 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 33348 KB Output is correct
2 Correct 795 ms 54892 KB Output is correct
3 Correct 489 ms 25284 KB Output is correct
4 Correct 857 ms 52540 KB Output is correct
5 Correct 811 ms 54008 KB Output is correct
6 Correct 502 ms 24148 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 332 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 320 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 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 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 7 ms 856 KB Output is correct
22 Correct 12 ms 1092 KB Output is correct
23 Correct 9 ms 844 KB Output is correct
24 Correct 8 ms 1104 KB Output is correct
25 Correct 10 ms 1244 KB Output is correct
26 Correct 8 ms 1112 KB Output is correct
27 Correct 11 ms 1408 KB Output is correct
28 Correct 12 ms 1364 KB Output is correct
29 Correct 12 ms 1436 KB Output is correct
30 Correct 20 ms 1620 KB Output is correct
31 Correct 18 ms 1880 KB Output is correct
32 Correct 17 ms 1876 KB Output is correct
33 Correct 120 ms 8672 KB Output is correct
34 Correct 110 ms 8848 KB Output is correct
35 Correct 124 ms 8248 KB Output is correct
36 Correct 270 ms 12532 KB Output is correct
37 Correct 273 ms 12264 KB Output is correct
38 Correct 265 ms 11184 KB Output is correct
39 Correct 315 ms 9012 KB Output is correct
40 Correct 329 ms 9056 KB Output is correct
41 Correct 297 ms 9124 KB Output is correct
42 Correct 124 ms 9200 KB Output is correct
43 Correct 259 ms 18396 KB Output is correct
44 Correct 206 ms 18428 KB Output is correct
45 Correct 201 ms 18380 KB Output is correct
46 Correct 225 ms 18340 KB Output is correct
47 Correct 209 ms 18420 KB Output is correct
48 Correct 241 ms 18424 KB Output is correct
49 Correct 217 ms 18316 KB Output is correct
50 Correct 266 ms 18340 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 332 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 320 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 328 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 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 6 ms 896 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 7 ms 856 KB Output is correct
22 Correct 12 ms 1092 KB Output is correct
23 Correct 9 ms 844 KB Output is correct
24 Correct 8 ms 1104 KB Output is correct
25 Correct 10 ms 1244 KB Output is correct
26 Correct 8 ms 1112 KB Output is correct
27 Correct 520 ms 22312 KB Output is correct
28 Correct 482 ms 22444 KB Output is correct
29 Correct 508 ms 24356 KB Output is correct
30 Correct 465 ms 23760 KB Output is correct
31 Correct 597 ms 26280 KB Output is correct
32 Correct 1085 ms 38844 KB Output is correct
33 Correct 673 ms 27996 KB Output is correct
34 Correct 732 ms 30088 KB Output is correct
35 Correct 1 ms 328 KB Output is correct
36 Correct 308 ms 9712 KB Output is correct
37 Correct 1174 ms 27988 KB Output is correct
38 Correct 1120 ms 28184 KB Output is correct
39 Correct 944 ms 24732 KB Output is correct
40 Correct 382 ms 14120 KB Output is correct
41 Correct 160 ms 8112 KB Output is correct
42 Correct 24 ms 2612 KB Output is correct
43 Correct 1124 ms 26932 KB Output is correct
44 Correct 1006 ms 24556 KB Output is correct
45 Correct 721 ms 33348 KB Output is correct
46 Correct 795 ms 54892 KB Output is correct
47 Correct 489 ms 25284 KB Output is correct
48 Correct 857 ms 52540 KB Output is correct
49 Correct 811 ms 54008 KB Output is correct
50 Correct 502 ms 24148 KB Output is correct
51 Correct 11 ms 1408 KB Output is correct
52 Correct 12 ms 1364 KB Output is correct
53 Correct 12 ms 1436 KB Output is correct
54 Correct 20 ms 1620 KB Output is correct
55 Correct 18 ms 1880 KB Output is correct
56 Correct 17 ms 1876 KB Output is correct
57 Correct 120 ms 8672 KB Output is correct
58 Correct 110 ms 8848 KB Output is correct
59 Correct 124 ms 8248 KB Output is correct
60 Correct 270 ms 12532 KB Output is correct
61 Correct 273 ms 12264 KB Output is correct
62 Correct 265 ms 11184 KB Output is correct
63 Correct 315 ms 9012 KB Output is correct
64 Correct 329 ms 9056 KB Output is correct
65 Correct 297 ms 9124 KB Output is correct
66 Correct 124 ms 9200 KB Output is correct
67 Correct 259 ms 18396 KB Output is correct
68 Correct 206 ms 18428 KB Output is correct
69 Correct 201 ms 18380 KB Output is correct
70 Correct 225 ms 18340 KB Output is correct
71 Correct 209 ms 18420 KB Output is correct
72 Correct 241 ms 18424 KB Output is correct
73 Correct 217 ms 18316 KB Output is correct
74 Correct 266 ms 18340 KB Output is correct
75 Correct 536 ms 22668 KB Output is correct
76 Correct 581 ms 22852 KB Output is correct
77 Correct 543 ms 24836 KB Output is correct
78 Correct 551 ms 24540 KB Output is correct
79 Correct 588 ms 22868 KB Output is correct
80 Correct 491 ms 24544 KB Output is correct
81 Correct 1179 ms 29108 KB Output is correct
82 Correct 1243 ms 30904 KB Output is correct
83 Correct 1145 ms 30812 KB Output is correct
84 Correct 1088 ms 27380 KB Output is correct
85 Correct 1205 ms 29744 KB Output is correct
86 Correct 1271 ms 31580 KB Output is correct
87 Correct 925 ms 25084 KB Output is correct
88 Correct 1144 ms 25856 KB Output is correct
89 Correct 1062 ms 28512 KB Output is correct
90 Correct 1164 ms 28424 KB Output is correct
91 Correct 1067 ms 28532 KB Output is correct
92 Correct 1069 ms 28592 KB Output is correct
93 Correct 1178 ms 60368 KB Output is correct
94 Correct 534 ms 30556 KB Output is correct
95 Correct 1320 ms 60644 KB Output is correct
96 Correct 1227 ms 59524 KB Output is correct
97 Correct 566 ms 29380 KB Output is correct
98 Correct 966 ms 44008 KB Output is correct
99 Correct 1293 ms 60752 KB Output is correct
100 Correct 884 ms 60720 KB Output is correct
101 Correct 1020 ms 37936 KB Output is correct
102 Correct 1213 ms 59436 KB Output is correct
103 Correct 578 ms 28956 KB Output is correct
104 Correct 1288 ms 60492 KB Output is correct
105 Correct 511 ms 30780 KB Output is correct
106 Correct 830 ms 54400 KB Output is correct
107 Correct 840 ms 54456 KB Output is correct
108 Correct 845 ms 54448 KB Output is correct
109 Correct 822 ms 54504 KB Output is correct
110 Correct 857 ms 54372 KB Output is correct
111 Correct 864 ms 54488 KB Output is correct
112 Correct 832 ms 54384 KB Output is correct
113 Correct 807 ms 54392 KB Output is correct
114 Correct 819 ms 54340 KB Output is correct
115 Correct 827 ms 54556 KB Output is correct
116 Correct 850 ms 59248 KB Output is correct