#include <bits/stdc++.h>
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
class rep {
struct Iter {
usize itr;
constexpr Iter(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept {
return itr != other.itr;
}
constexpr usize operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr rep(const usize first, const usize last) noexcept
: first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
constexpr u64 ceil_log2(const u64 x) {
u64 e = 0;
while (((u64)1 << e) < x) ++e;
return e;
}
template <class T> using Vec = std::vector<T>;
constexpr i64 MAX = 1000000000;
constexpr i64 square(const i64 x) { return x * x; }
void APIO18_circle_selection_main() {
usize N;
std::cin >> N;
Vec<i64> X(N), Y(N), R(N);
for (const auto i : rep(0, N)) {
std::cin >> X[i] >> Y[i] >> R[i];
X[i] += MAX;
Y[i] += MAX;
}
const auto intersect = [&](const usize i, const usize j) {
return square(X[i] - X[j]) + square(Y[i] - Y[j]) <= square(R[i] + R[j]);
};
i64 G = (i64)1 << ceil_log2(2 * MAX);
Vec<i64> unit;
unit.push_back(0);
Vec<usize> order(N);
std::iota(order.begin(), order.end(), (usize)0);
std::sort(order.begin(), order.end(),
[&](const usize i, const usize j) { return Y[i] < Y[j]; });
Vec<Vec<usize>> group;
group.push_back(order);
std::sort(order.begin(), order.end(), [&](const usize i, const usize j) {
return R[i] > R[j] or (R[i] == R[j] and i < j);
});
Vec<usize> ans(N);
std::iota(ans.begin(), ans.end(), (usize)0);
Vec<bool> done(N);
for (const auto center : order) {
if (done[center]) {
continue;
}
done[center] = true;
while (G / 2 >= R[center]) {
G /= 2;
Vec<i64> new_unit;
Vec<Vec<usize>> new_group;
for (const auto i : rep(0, unit.size())) {
const auto to_left = 2 * unit[i];
const auto itr = std::stable_partition(
group[i].begin(), group[i].end(),
[&](const usize i) { return X[i] / G == to_left; });
if (itr != group[i].begin()) {
new_unit.push_back(to_left);
new_group.emplace_back(group[i].begin(), itr);
}
if (itr != group[i].end()) {
new_unit.push_back(to_left + 1);
new_group.emplace_back(itr, group[i].end());
}
}
unit = std::move(new_unit);
group = std::move(new_group);
}
const auto X_c = X[center] / G;
const isize X_i =
std::lower_bound(unit.begin(), unit.end(), X_c) - unit.begin();
for (isize di = -2; di <= 2; ++di) {
const auto i = X_i + di;
if (i < 0 or i >= (isize)unit.size() or
std::abs(unit[i] - X_c) > 2) {
continue;
}
auto itr = std::partition_point(
group[i].begin(), group[i].end(), [&](const usize k) {
return Y[k] + 2 * R[center] < Y[center];
});
while (itr != group[i].end()) {
const auto k = *itr;
if (Y[k] - 2 * R[center] > Y[center]) {
break;
}
if (!done[k] and intersect(center, k)) {
ans[k] = center;
done[k] = true;
}
++itr;
}
}
}
for (const auto x : ans) {
std::cout << x + 1 << '\n';
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
APIO18_circle_selection_main();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
280 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
588 KB |
Output is correct |
20 |
Correct |
4 ms |
588 KB |
Output is correct |
21 |
Correct |
4 ms |
588 KB |
Output is correct |
22 |
Correct |
12 ms |
1624 KB |
Output is correct |
23 |
Correct |
12 ms |
1544 KB |
Output is correct |
24 |
Correct |
14 ms |
1592 KB |
Output is correct |
25 |
Correct |
15 ms |
1684 KB |
Output is correct |
26 |
Correct |
13 ms |
1592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
19576 KB |
Output is correct |
2 |
Correct |
221 ms |
19664 KB |
Output is correct |
3 |
Correct |
192 ms |
19852 KB |
Output is correct |
4 |
Correct |
193 ms |
19412 KB |
Output is correct |
5 |
Correct |
367 ms |
38032 KB |
Output is correct |
6 |
Correct |
662 ms |
69184 KB |
Output is correct |
7 |
Correct |
505 ms |
60560 KB |
Output is correct |
8 |
Correct |
526 ms |
62944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
319 ms |
23924 KB |
Output is correct |
3 |
Correct |
1114 ms |
75532 KB |
Output is correct |
4 |
Correct |
1099 ms |
80016 KB |
Output is correct |
5 |
Correct |
985 ms |
75104 KB |
Output is correct |
6 |
Correct |
240 ms |
20736 KB |
Output is correct |
7 |
Correct |
115 ms |
10668 KB |
Output is correct |
8 |
Correct |
30 ms |
3780 KB |
Output is correct |
9 |
Correct |
1060 ms |
81272 KB |
Output is correct |
10 |
Correct |
452 ms |
23360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
443 ms |
23344 KB |
Output is correct |
2 |
Correct |
853 ms |
72344 KB |
Output is correct |
3 |
Correct |
290 ms |
19008 KB |
Output is correct |
4 |
Correct |
582 ms |
58380 KB |
Output is correct |
5 |
Correct |
622 ms |
63412 KB |
Output is correct |
6 |
Correct |
264 ms |
19500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
280 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
588 KB |
Output is correct |
20 |
Correct |
4 ms |
588 KB |
Output is correct |
21 |
Correct |
4 ms |
588 KB |
Output is correct |
22 |
Correct |
12 ms |
1624 KB |
Output is correct |
23 |
Correct |
12 ms |
1544 KB |
Output is correct |
24 |
Correct |
14 ms |
1592 KB |
Output is correct |
25 |
Correct |
15 ms |
1684 KB |
Output is correct |
26 |
Correct |
13 ms |
1592 KB |
Output is correct |
27 |
Correct |
9 ms |
972 KB |
Output is correct |
28 |
Correct |
7 ms |
972 KB |
Output is correct |
29 |
Correct |
7 ms |
960 KB |
Output is correct |
30 |
Correct |
24 ms |
2840 KB |
Output is correct |
31 |
Correct |
25 ms |
2900 KB |
Output is correct |
32 |
Correct |
26 ms |
2744 KB |
Output is correct |
33 |
Correct |
75 ms |
5796 KB |
Output is correct |
34 |
Correct |
73 ms |
5812 KB |
Output is correct |
35 |
Correct |
109 ms |
11472 KB |
Output is correct |
36 |
Correct |
284 ms |
23284 KB |
Output is correct |
37 |
Correct |
302 ms |
21772 KB |
Output is correct |
38 |
Correct |
289 ms |
23932 KB |
Output is correct |
39 |
Correct |
180 ms |
7104 KB |
Output is correct |
40 |
Correct |
176 ms |
7384 KB |
Output is correct |
41 |
Correct |
195 ms |
7384 KB |
Output is correct |
42 |
Correct |
96 ms |
6868 KB |
Output is correct |
43 |
Correct |
168 ms |
19756 KB |
Output is correct |
44 |
Correct |
181 ms |
20028 KB |
Output is correct |
45 |
Correct |
169 ms |
19712 KB |
Output is correct |
46 |
Correct |
175 ms |
19664 KB |
Output is correct |
47 |
Correct |
169 ms |
20280 KB |
Output is correct |
48 |
Correct |
166 ms |
19784 KB |
Output is correct |
49 |
Correct |
168 ms |
20048 KB |
Output is correct |
50 |
Correct |
166 ms |
19680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
280 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
588 KB |
Output is correct |
20 |
Correct |
4 ms |
588 KB |
Output is correct |
21 |
Correct |
4 ms |
588 KB |
Output is correct |
22 |
Correct |
12 ms |
1624 KB |
Output is correct |
23 |
Correct |
12 ms |
1544 KB |
Output is correct |
24 |
Correct |
14 ms |
1592 KB |
Output is correct |
25 |
Correct |
15 ms |
1684 KB |
Output is correct |
26 |
Correct |
13 ms |
1592 KB |
Output is correct |
27 |
Correct |
199 ms |
19576 KB |
Output is correct |
28 |
Correct |
221 ms |
19664 KB |
Output is correct |
29 |
Correct |
192 ms |
19852 KB |
Output is correct |
30 |
Correct |
193 ms |
19412 KB |
Output is correct |
31 |
Correct |
367 ms |
38032 KB |
Output is correct |
32 |
Correct |
662 ms |
69184 KB |
Output is correct |
33 |
Correct |
505 ms |
60560 KB |
Output is correct |
34 |
Correct |
526 ms |
62944 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
319 ms |
23924 KB |
Output is correct |
37 |
Correct |
1114 ms |
75532 KB |
Output is correct |
38 |
Correct |
1099 ms |
80016 KB |
Output is correct |
39 |
Correct |
985 ms |
75104 KB |
Output is correct |
40 |
Correct |
240 ms |
20736 KB |
Output is correct |
41 |
Correct |
115 ms |
10668 KB |
Output is correct |
42 |
Correct |
30 ms |
3780 KB |
Output is correct |
43 |
Correct |
1060 ms |
81272 KB |
Output is correct |
44 |
Correct |
452 ms |
23360 KB |
Output is correct |
45 |
Correct |
443 ms |
23344 KB |
Output is correct |
46 |
Correct |
853 ms |
72344 KB |
Output is correct |
47 |
Correct |
290 ms |
19008 KB |
Output is correct |
48 |
Correct |
582 ms |
58380 KB |
Output is correct |
49 |
Correct |
622 ms |
63412 KB |
Output is correct |
50 |
Correct |
264 ms |
19500 KB |
Output is correct |
51 |
Correct |
9 ms |
972 KB |
Output is correct |
52 |
Correct |
7 ms |
972 KB |
Output is correct |
53 |
Correct |
7 ms |
960 KB |
Output is correct |
54 |
Correct |
24 ms |
2840 KB |
Output is correct |
55 |
Correct |
25 ms |
2900 KB |
Output is correct |
56 |
Correct |
26 ms |
2744 KB |
Output is correct |
57 |
Correct |
75 ms |
5796 KB |
Output is correct |
58 |
Correct |
73 ms |
5812 KB |
Output is correct |
59 |
Correct |
109 ms |
11472 KB |
Output is correct |
60 |
Correct |
284 ms |
23284 KB |
Output is correct |
61 |
Correct |
302 ms |
21772 KB |
Output is correct |
62 |
Correct |
289 ms |
23932 KB |
Output is correct |
63 |
Correct |
180 ms |
7104 KB |
Output is correct |
64 |
Correct |
176 ms |
7384 KB |
Output is correct |
65 |
Correct |
195 ms |
7384 KB |
Output is correct |
66 |
Correct |
96 ms |
6868 KB |
Output is correct |
67 |
Correct |
168 ms |
19756 KB |
Output is correct |
68 |
Correct |
181 ms |
20028 KB |
Output is correct |
69 |
Correct |
169 ms |
19712 KB |
Output is correct |
70 |
Correct |
175 ms |
19664 KB |
Output is correct |
71 |
Correct |
169 ms |
20280 KB |
Output is correct |
72 |
Correct |
166 ms |
19784 KB |
Output is correct |
73 |
Correct |
168 ms |
20048 KB |
Output is correct |
74 |
Correct |
166 ms |
19680 KB |
Output is correct |
75 |
Correct |
315 ms |
20900 KB |
Output is correct |
76 |
Correct |
261 ms |
20484 KB |
Output is correct |
77 |
Correct |
240 ms |
19136 KB |
Output is correct |
78 |
Correct |
230 ms |
16936 KB |
Output is correct |
79 |
Correct |
423 ms |
37204 KB |
Output is correct |
80 |
Correct |
232 ms |
17028 KB |
Output is correct |
81 |
Correct |
1022 ms |
68124 KB |
Output is correct |
82 |
Correct |
1081 ms |
85468 KB |
Output is correct |
83 |
Correct |
1054 ms |
70096 KB |
Output is correct |
84 |
Correct |
983 ms |
76388 KB |
Output is correct |
85 |
Correct |
1050 ms |
75828 KB |
Output is correct |
86 |
Correct |
1100 ms |
82100 KB |
Output is correct |
87 |
Correct |
923 ms |
66648 KB |
Output is correct |
88 |
Correct |
900 ms |
21148 KB |
Output is correct |
89 |
Correct |
893 ms |
21188 KB |
Output is correct |
90 |
Correct |
843 ms |
21264 KB |
Output is correct |
91 |
Correct |
866 ms |
21268 KB |
Output is correct |
92 |
Correct |
886 ms |
21184 KB |
Output is correct |
93 |
Correct |
876 ms |
71772 KB |
Output is correct |
94 |
Correct |
521 ms |
20132 KB |
Output is correct |
95 |
Correct |
888 ms |
78996 KB |
Output is correct |
96 |
Correct |
862 ms |
83912 KB |
Output is correct |
97 |
Correct |
673 ms |
20260 KB |
Output is correct |
98 |
Correct |
705 ms |
65620 KB |
Output is correct |
99 |
Correct |
958 ms |
81940 KB |
Output is correct |
100 |
Correct |
958 ms |
77480 KB |
Output is correct |
101 |
Correct |
698 ms |
62592 KB |
Output is correct |
102 |
Correct |
894 ms |
75436 KB |
Output is correct |
103 |
Correct |
736 ms |
20972 KB |
Output is correct |
104 |
Correct |
1053 ms |
80128 KB |
Output is correct |
105 |
Correct |
350 ms |
19320 KB |
Output is correct |
106 |
Correct |
497 ms |
41216 KB |
Output is correct |
107 |
Correct |
482 ms |
42212 KB |
Output is correct |
108 |
Correct |
482 ms |
42220 KB |
Output is correct |
109 |
Correct |
481 ms |
42272 KB |
Output is correct |
110 |
Correct |
494 ms |
44064 KB |
Output is correct |
111 |
Correct |
487 ms |
41412 KB |
Output is correct |
112 |
Correct |
476 ms |
42132 KB |
Output is correct |
113 |
Correct |
496 ms |
42164 KB |
Output is correct |
114 |
Correct |
494 ms |
42116 KB |
Output is correct |
115 |
Correct |
482 ms |
43256 KB |
Output is correct |
116 |
Correct |
537 ms |
58832 KB |
Output is correct |