#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
constexpr int LOG = 30;
int main() {
int N;
std::cin >> N;
vector<int> X(N), Y(N), R(N);
for (int i = 0; i < N; ++i) {
std::cin >> X[i] >> Y[i] >> R[i];
}
int logR = LOG;
vector<int> xs = {0};
vector<vector<int>> pts = {{}};
for (int i = 0; i < N; ++i) {
pts[0].push_back(i);
}
std::sort(pts[0].begin(), pts[0].end(),
[&](const int i, const int j) { return Y[i] < Y[j]; });
vector<int> order(N), ans(N, -1);
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(),
[&](const int i, const int j) { return R[i] != R[j] ? R[i] > R[j] : i < j; });
for (const int i : order) {
if (ans[i] != -1) {
continue;
}
while (R[i] <= (1 << (logR - 1))) {
logR -= 1;
vector<int> next_xs;
vector<vector<int>> next_pts;
for (int i = 0; i < (int)xs.size(); ++i) {
array<vector<int>, 2> arr;
for (const int j : pts[i]) {
arr[Y[j] >> logR & 1].push_back(j);
}
for (int k = 0; k < 2; ++k) {
if (!arr[k].empty()) {
next_xs.push_back(xs[i] * 2 + k);
next_pts.push_back(std::move(arr[k]));
}
}
}
xs = std::move(next_xs);
pts = std::move(next_pts);
}
ans[i] = i;
int xi = std::lower_bound(xs.begin(), xs.end(), (X[i] >> logR) - 2) - xs.begin();
while (xi < (int)xs.size() && xs[xi] <= (X[i] >> logR) + 2) {
const auto& ys = pts[xi];
int yi = std::partition_point(ys.begin(), ys.end(),
[&](const int j) { return Y[i] - Y[j] > 2 * R[i]; }) -
ys.begin();
while (yi < (int)ys.size() && Y[ys[yi]] - Y[i] <= 2 * R[i]) {
const int j = ys[yi];
if (ans[j] == -1) {
const long long dx = X[i] - X[j];
const long long dy = Y[i] - Y[j];
const long long r = R[i] + R[j];
if (dx * dx + dy * dy <= r * r) {
ans[j] = i;
}
}
yi += 1;
}
xi += 1;
}
}
for (int i = 0; i < N; ++i) {
std::cout << ans[i] + 1 << " \n"[i + 1 == N];
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
395 ms |
12708 KB |
Output is correct |
2 |
Correct |
388 ms |
12852 KB |
Output is correct |
3 |
Correct |
362 ms |
11308 KB |
Output is correct |
4 |
Incorrect |
387 ms |
12732 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
539 ms |
18232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |