#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define int long long
using namespace std;
const int MAXN = (int)3e5 + 5;
int n;
int x[MAXN];
int y[MAXN];
int rad[MAXN];
vector <int> g[MAXN];
double get_dist(int i, int j) {
return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}
bool intersect(int i, int j) {
return (get_dist(i, j) <= (rad[i] + rad[j]) * (rad[i] + rad[j]));
}
int ans[MAXN];
vector <int> pos;
void subtask1() {
for (int i = 0; i < n; i++) {
pos.pb(i);
}
sort(all(pos), [&](int A, int B) {
if (rad[A] != rad[B]) {
return rad[A] > rad[B];
} else {
return A < B;
}
});
memset(ans, -1, sizeof(ans));
for (int el : pos) {
if (ans[el] == -1) {
ans[el] = el;
for (int i = 1; i <= n; i++) {
if (ans[i] == -1 && intersect(i, el)) {
ans[i] = el;
}
}
}
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
exit(0);
}
struct node {
int x, y, rad;
int ind;
node () {
}
node (int x_, int y_, int rad_, int ind_) {
x = x_;
y = y_;
rad = rad_;
ind = ind_;
}
const bool operator < (const node &other) {
return x < other.x;
}
};
signed main() {
fastInp;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> rad[i];
}
if (n <= 5000) {
subtask1();
}
else {
vector <node> vec;
for (int i = 0; i < n; i++) {
vec.pb(node(x[i], y[i], rad[i], i));
}
sort(all(vec));
for (int i = 0; i < n; i++) {
pos.pb(i);
}
sort(all(pos), [&](int A, int B) {
if (vec[A].rad != vec[B].rad) {
return vec[A].rad > vec[B].rad;
} else {
return vec[A].ind < vec[B].ind;
}
});
memset(ans, -1, sizeof(ans));
vector <int> block(1000, -1);
int S = sqrt(n);
if (S * S < n) {
S++;
}
for (int order : pos) {
if (ans[vec[order].ind] != -1) {
continue;
}
if (block[order / S] != -1) {
continue;
}
int x = vec[order].x;
int rad = vec[order].rad;
int lp = x - rad;
int rp = x + rad;
int l = -1, r = order;
int lft, rgt;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (vec[mid].x >= lp) {
r = mid;
} else {
l = mid;
}
}
lft = r;
l = order, r = n; // 0-index
while (r - l > 1) {
int mid = (l + r) >> 1;
if (vec[mid].x <= rp) {
l = mid;
} else {
r = mid;
}
}
rgt = l;
// update in sqrt decomposition
if (lft % S != 0) {
for (int j = lft; j < (lft / S + 1) * S; j++) {
if (block[j / S] != -1 || ans[vec[j].ind] != -1) {
continue;
}
ans[vec[j].ind] = vec[order].ind;
}
}
if ((rgt + 1) % S != 0) {
for (int j = rgt; j >= (rgt / S) * S; j--) {
if (block[j / S] != -1 || ans[vec[j].ind] != -1) {
continue;
}
ans[vec[j].ind] = vec[order].ind;
}
}
int l_block = (lft % S != 0 ? lft / S + 1 : lft / S);
int r_block = ((rgt + 1) % S != 0 ? rgt / S - 1 : rgt / S);
for (int j = l_block; j <= r_block; j++) {
if (block[j] == -1) {
block[j] = vec[order].ind;
}
}
}
for (int i = 0; i < n; i++) {
if (ans[i] != -1) {
cout << ans[i] << " ";
} else {
cout << block[i / S] << " ";
}
}
}
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
34688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
313 ms |
33684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
