#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
template<class... Args>
vec(size_t n = 0, Args... args)
: vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
template<class... Args>
vec(Args... args)
: vector<T>(args...) {}
};
template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
struct Circle {
int x, y, r;
Circle(int t_x = 0, int t_y = 0, int t_r = 0)
: x(t_x),
y(t_y),
r(t_r) {}
bool CheckIntersection(const Circle& o) const {
return static_cast<int64_t>(x - o.x) * (x - o.x) + static_cast<int64_t>(y - o.y) * (y - o.y) <= static_cast<int64_t>(r + o.r) * (r + o.r);
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n_circles; cin >> n_circles;
vec<Circle, 1> circles(n_circles);
int min_x, min_y;
min_x = min_y = numeric_limits<int>::max();
for (auto& circle : circles) {
cin >> circle.x >> circle.y >> circle.r;
Minimize(min_x, circle.x);
Minimize(min_y, circle.y);
}
for (auto& circle : circles) {
circle.x -= min_x;
circle.y -= min_y;
}
vec<int, 1> ord_circles(n_circles); iota(ALL(ord_circles), 0);
sort(ALL(ord_circles), [&](int i, int j) {
return circles[i].r != circles[j].r ? circles[i].r > circles[j].r : i < j;
});
int scaler = 31;
vec<pair<int, int>, 2> members_groups(1);
for (int i = 0; i < n_circles; ++i) {
members_groups[0].emplace_back(circles[i].y, i);
}
sort(ALL(members_groups[0]));
vec<bool, 1> deleted(n_circles);
vec<int, 1> answers(n_circles);
for (auto& idx_circle : ord_circles) {
if (!deleted[idx_circle]) {
deleted[idx_circle] = true;
answers[idx_circle] = idx_circle;
while (scaler && circles[idx_circle].r < (1 << (scaler - 1))) {
--scaler;
vec<pair<int, int>, 2> next_members_groups;
for (auto& members : members_groups) {
array<vec<pair<int, int>, 1>, 2> tmp_members;
for (auto& member : members) {
if (deleted[member.second]) {
continue;
}
tmp_members[(circles[member.second].x >> scaler) & 1].emplace_back(member);
}
if (SZ(tmp_members[0])) {
next_members_groups.emplace_back(tmp_members[0]);
}
if (SZ(tmp_members[1])) {
next_members_groups.emplace_back(tmp_members[1]);
}
}
members_groups.swap(next_members_groups);
}
for (auto it_members_groups = lower_bound(ALL(members_groups), (circles[idx_circle].x >> scaler) - 2, [&](vec<pair<int, int>, 1> i, int j) { return (circles[i[0].second].x >> scaler) < j; }); it_members_groups != members_groups.end() && (circles[(*it_members_groups)[0].second].x >> scaler) <= (circles[idx_circle].x >> scaler) + 2; ++it_members_groups) {
for (auto it_members = lower_bound(ALL(*it_members_groups), (circles[idx_circle].y >> scaler) - 2, [&](pair<int, int> i, int j) { return (i.first >> scaler) < j; });
it_members != it_members_groups->end() && (it_members->first >> scaler) <= (circles[idx_circle].y >> scaler) + 2; ++it_members) {
if (!deleted[it_members->second] && circles[idx_circle].CheckIntersection(circles[it_members->second])) {
deleted[it_members->second] = true;
answers[it_members->second] = idx_circle;
}
}
}
}
}
for (auto& answer : answers) {
cout << answer + 1 << ' ';
}
cout << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
416 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
4 ms |
768 KB |
Output is correct |
20 |
Correct |
4 ms |
768 KB |
Output is correct |
21 |
Correct |
4 ms |
768 KB |
Output is correct |
22 |
Correct |
10 ms |
896 KB |
Output is correct |
23 |
Correct |
11 ms |
768 KB |
Output is correct |
24 |
Correct |
11 ms |
1020 KB |
Output is correct |
25 |
Correct |
13 ms |
1260 KB |
Output is correct |
26 |
Correct |
10 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
211 ms |
17132 KB |
Output is correct |
2 |
Correct |
206 ms |
17356 KB |
Output is correct |
3 |
Correct |
209 ms |
22300 KB |
Output is correct |
4 |
Correct |
200 ms |
21564 KB |
Output is correct |
5 |
Correct |
348 ms |
20804 KB |
Output is correct |
6 |
Correct |
711 ms |
26784 KB |
Output is correct |
7 |
Correct |
383 ms |
21860 KB |
Output is correct |
8 |
Correct |
544 ms |
21452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
244 ms |
8052 KB |
Output is correct |
3 |
Correct |
1025 ms |
20680 KB |
Output is correct |
4 |
Correct |
1130 ms |
22596 KB |
Output is correct |
5 |
Correct |
850 ms |
19308 KB |
Output is correct |
6 |
Correct |
314 ms |
12456 KB |
Output is correct |
7 |
Correct |
149 ms |
6968 KB |
Output is correct |
8 |
Correct |
30 ms |
2164 KB |
Output is correct |
9 |
Correct |
1020 ms |
22064 KB |
Output is correct |
10 |
Correct |
892 ms |
19008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
978 ms |
19608 KB |
Output is correct |
2 |
Correct |
1859 ms |
57744 KB |
Output is correct |
3 |
Correct |
421 ms |
17996 KB |
Output is correct |
4 |
Correct |
1676 ms |
52520 KB |
Output is correct |
5 |
Correct |
1818 ms |
53408 KB |
Output is correct |
6 |
Correct |
390 ms |
26060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
416 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
4 ms |
768 KB |
Output is correct |
20 |
Correct |
4 ms |
768 KB |
Output is correct |
21 |
Correct |
4 ms |
768 KB |
Output is correct |
22 |
Correct |
10 ms |
896 KB |
Output is correct |
23 |
Correct |
11 ms |
768 KB |
Output is correct |
24 |
Correct |
11 ms |
1020 KB |
Output is correct |
25 |
Correct |
13 ms |
1260 KB |
Output is correct |
26 |
Correct |
10 ms |
1024 KB |
Output is correct |
27 |
Correct |
8 ms |
1152 KB |
Output is correct |
28 |
Correct |
8 ms |
1280 KB |
Output is correct |
29 |
Correct |
10 ms |
1200 KB |
Output is correct |
30 |
Correct |
19 ms |
1308 KB |
Output is correct |
31 |
Correct |
20 ms |
1596 KB |
Output is correct |
32 |
Correct |
22 ms |
1676 KB |
Output is correct |
33 |
Correct |
88 ms |
7920 KB |
Output is correct |
34 |
Correct |
84 ms |
7920 KB |
Output is correct |
35 |
Correct |
92 ms |
8768 KB |
Output is correct |
36 |
Correct |
274 ms |
11192 KB |
Output is correct |
37 |
Correct |
279 ms |
10420 KB |
Output is correct |
38 |
Correct |
246 ms |
9396 KB |
Output is correct |
39 |
Correct |
322 ms |
7072 KB |
Output is correct |
40 |
Correct |
313 ms |
7096 KB |
Output is correct |
41 |
Correct |
309 ms |
6836 KB |
Output is correct |
42 |
Correct |
190 ms |
7544 KB |
Output is correct |
43 |
Correct |
314 ms |
19044 KB |
Output is correct |
44 |
Correct |
307 ms |
17528 KB |
Output is correct |
45 |
Correct |
322 ms |
19136 KB |
Output is correct |
46 |
Correct |
295 ms |
19072 KB |
Output is correct |
47 |
Correct |
302 ms |
19068 KB |
Output is correct |
48 |
Correct |
354 ms |
19064 KB |
Output is correct |
49 |
Correct |
352 ms |
19064 KB |
Output is correct |
50 |
Correct |
400 ms |
19060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
416 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
4 ms |
768 KB |
Output is correct |
20 |
Correct |
4 ms |
768 KB |
Output is correct |
21 |
Correct |
4 ms |
768 KB |
Output is correct |
22 |
Correct |
10 ms |
896 KB |
Output is correct |
23 |
Correct |
11 ms |
768 KB |
Output is correct |
24 |
Correct |
11 ms |
1020 KB |
Output is correct |
25 |
Correct |
13 ms |
1260 KB |
Output is correct |
26 |
Correct |
10 ms |
1024 KB |
Output is correct |
27 |
Correct |
211 ms |
17132 KB |
Output is correct |
28 |
Correct |
206 ms |
17356 KB |
Output is correct |
29 |
Correct |
209 ms |
22300 KB |
Output is correct |
30 |
Correct |
200 ms |
21564 KB |
Output is correct |
31 |
Correct |
348 ms |
20804 KB |
Output is correct |
32 |
Correct |
711 ms |
26784 KB |
Output is correct |
33 |
Correct |
383 ms |
21860 KB |
Output is correct |
34 |
Correct |
544 ms |
21452 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
244 ms |
8052 KB |
Output is correct |
37 |
Correct |
1025 ms |
20680 KB |
Output is correct |
38 |
Correct |
1130 ms |
22596 KB |
Output is correct |
39 |
Correct |
850 ms |
19308 KB |
Output is correct |
40 |
Correct |
314 ms |
12456 KB |
Output is correct |
41 |
Correct |
149 ms |
6968 KB |
Output is correct |
42 |
Correct |
30 ms |
2164 KB |
Output is correct |
43 |
Correct |
1020 ms |
22064 KB |
Output is correct |
44 |
Correct |
892 ms |
19008 KB |
Output is correct |
45 |
Correct |
978 ms |
19608 KB |
Output is correct |
46 |
Correct |
1859 ms |
57744 KB |
Output is correct |
47 |
Correct |
421 ms |
17996 KB |
Output is correct |
48 |
Correct |
1676 ms |
52520 KB |
Output is correct |
49 |
Correct |
1818 ms |
53408 KB |
Output is correct |
50 |
Correct |
390 ms |
26060 KB |
Output is correct |
51 |
Correct |
8 ms |
1152 KB |
Output is correct |
52 |
Correct |
8 ms |
1280 KB |
Output is correct |
53 |
Correct |
10 ms |
1200 KB |
Output is correct |
54 |
Correct |
19 ms |
1308 KB |
Output is correct |
55 |
Correct |
20 ms |
1596 KB |
Output is correct |
56 |
Correct |
22 ms |
1676 KB |
Output is correct |
57 |
Correct |
88 ms |
7920 KB |
Output is correct |
58 |
Correct |
84 ms |
7920 KB |
Output is correct |
59 |
Correct |
92 ms |
8768 KB |
Output is correct |
60 |
Correct |
274 ms |
11192 KB |
Output is correct |
61 |
Correct |
279 ms |
10420 KB |
Output is correct |
62 |
Correct |
246 ms |
9396 KB |
Output is correct |
63 |
Correct |
322 ms |
7072 KB |
Output is correct |
64 |
Correct |
313 ms |
7096 KB |
Output is correct |
65 |
Correct |
309 ms |
6836 KB |
Output is correct |
66 |
Correct |
190 ms |
7544 KB |
Output is correct |
67 |
Correct |
314 ms |
19044 KB |
Output is correct |
68 |
Correct |
307 ms |
17528 KB |
Output is correct |
69 |
Correct |
322 ms |
19136 KB |
Output is correct |
70 |
Correct |
295 ms |
19072 KB |
Output is correct |
71 |
Correct |
302 ms |
19068 KB |
Output is correct |
72 |
Correct |
354 ms |
19064 KB |
Output is correct |
73 |
Correct |
352 ms |
19064 KB |
Output is correct |
74 |
Correct |
400 ms |
19060 KB |
Output is correct |
75 |
Correct |
296 ms |
24116 KB |
Output is correct |
76 |
Correct |
301 ms |
23824 KB |
Output is correct |
77 |
Correct |
348 ms |
26188 KB |
Output is correct |
78 |
Correct |
289 ms |
23728 KB |
Output is correct |
79 |
Correct |
413 ms |
23932 KB |
Output is correct |
80 |
Correct |
321 ms |
23780 KB |
Output is correct |
81 |
Correct |
1108 ms |
26640 KB |
Output is correct |
82 |
Correct |
1226 ms |
26748 KB |
Output is correct |
83 |
Correct |
1139 ms |
26308 KB |
Output is correct |
84 |
Correct |
984 ms |
25760 KB |
Output is correct |
85 |
Correct |
1060 ms |
26648 KB |
Output is correct |
86 |
Correct |
1177 ms |
28220 KB |
Output is correct |
87 |
Correct |
1374 ms |
23676 KB |
Output is correct |
88 |
Correct |
1422 ms |
20760 KB |
Output is correct |
89 |
Correct |
1331 ms |
18764 KB |
Output is correct |
90 |
Correct |
1596 ms |
21088 KB |
Output is correct |
91 |
Correct |
1365 ms |
20992 KB |
Output is correct |
92 |
Correct |
1382 ms |
19432 KB |
Output is correct |
93 |
Correct |
1769 ms |
53944 KB |
Output is correct |
94 |
Execution timed out |
3069 ms |
22844 KB |
Time limit exceeded |
95 |
Halted |
0 ms |
0 KB |
- |