#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const int MAX_N = 3e5+5;
int n;
ll X[MAX_N], Y[MAX_N], R[MAX_N];
int P[MAX_N];
bool visited[MAX_N];
struct Quad
{
ll l, r, bot, top;
array<Quad*, 4> childs = {};
int idx;
int sz;
Quad()
{
}
Quad(ll _l, ll _r, ll _bot, ll _top)
: l(_l), r(_r), bot(_bot), top(_top)
{
idx = -1;
sz = 0;
}
void add(int x, int y, int idx)
{
if(x < l || x > r || y < bot || y > top) {
return;
}
sz++;
// cerr << "l = " << l << ", r = " << r << ", "
// << "bot = " << bot << ", top = " << top << "\n";
if(l == r && bot == top) {
this->idx = idx;
}
else {
ll midH, midV;
midH = l+(r-l)/2;
midV = bot+(top-bot)/2;
if(l != r && top != bot) {
if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > midV)) {
childs[0] = new Quad(l, midH, bot, midV);
}
else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > midV)) {
childs[1] = new Quad(midH+1, r, bot, midV);
}
else if(childs[2] == nullptr && !(x < l || x > midH || y < midV+1 || y > top)) {
childs[2] = new Quad(l, midH, midV+1, top);
}
else if(childs[3] == nullptr && !(x < midH+1 || x > r || y < midV+1 || y > top)) {
childs[3] = new Quad(midH+1, r, midV+1, top);
}
}
else if(l != r) {
if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > top)) {
childs[0] = new Quad(l, midH, bot, midV);
}
else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > top)) {
childs[1] = new Quad(midH+1, r, bot, top);
}
}
else if(top != bot) {
if(childs[0] == nullptr && !(x < l || x > r || y < bot || y > midV)) {
childs[0] = new Quad(l, r, bot, midV);
}
else if(childs[1] == nullptr && !(x < l || x > r || y < midV+1 || y > top)) {
childs[1] = new Quad(l, r, midV+1, top);
}
}
for(int k = 0; k < 4; k++) {
if(childs[k] != nullptr) {
childs[k]->add(x, y, idx);
}
}
}
}
void setInRange(int x, int y, int radius, int idx)
{
if(x+2*radius < l || x-2*radius > r || y+2*radius < bot || y-2*radius > top || sz == 0) {
return;
}
// cerr << "l = " << l << ", r = " << r << ", "
// << "bot = " << bot << ", top = " << top << "\n";
if(l == r && bot == top) {
if((R[idx]+R[this->idx])*(R[idx]+R[this->idx])
>= llabs(X[idx]-X[this->idx])*llabs(X[idx]-X[this->idx])
+llabs(Y[idx]-Y[this->idx])*llabs(Y[idx]-Y[this->idx])) {
P[this->idx] = idx;
visited[this->idx] = true;
sz--;
}
return;
}
int cnt = 0;
for(int k = 0; k < 4; k++) {
if(childs[k] != nullptr) {
childs[k]->setInRange(x, y, radius, idx);
cnt += childs[k]->sz;
}
}
sz = cnt;
}
};
Quad Q(-1000000000, 1000000000, -1000000000, 1000000000);
int main()
{
// cerr << "0:\n";
// Q.add(0, 0, 0);
// cerr << "1:\n";
// Q.add(2, 2, 1);
// cerr << "2:\n";
// Q.add(-3, -3, 2);
//
// cerr << "P:\n";
// Q.setInRange(0, 1, 1, 3);
// for(int i = 0; i < 3; i++) {
// cerr << i << ": " << P[i] << "\n";
// }
cin >> n;
for(int i = 0; i < n; i++) {
cin >> X[i] >> Y[i] >> R[i];
}
iota(P, P+n, 0);
// *Don't* handle circles at the same position
// map<pair<int, int>, int> M;
// for(int i = 0; i < n; i++) {
// auto it = M.find({X[i], Y[i]});
// if(it != M.end()) {
// if(R[it->second] < R[i]) {
// visited[it->second] = true;
// P[it->second] = i;
// M[{X[i], Y[i]}] = i;
// }
// else {
// visited[i] = true;
// P[i] = it->second;
// }
// }
// else {
// M[{X[i], Y[i]}] = i;
// }
// }
for(int i = 0; i < n; i++) {
//cerr << i << " started\n";
Q.add(X[i], Y[i], i);
//cerr << i << " finished\n";
}
vector<int> I(n);
iota(I.begin(), I.end(), 0);
sort(I.begin(), I.end(),
[&](int a, int b)
{
return R[a] > R[b] || (R[a] == R[b] && a < b);
});
for(int i = 0; i < n; i++) {
int idx = I[i];
if(visited[idx]) continue;
Q.setInRange(X[idx], Y[idx], R[idx], idx);
}
// for(int i = 0; i < n; i++) {
// cerr << i << ": " << P[i] << "\n";
// }
for(int i = 0; i < n; i++) {
cout << 1+P[i] << " ";
}
cout << "\n";
return 0;
}
/*
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
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Incorrect |
1 ms |
428 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1149 ms |
303848 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
292 KB |
Output is correct |
2 |
Correct |
594 ms |
190852 KB |
Output is correct |
3 |
Correct |
1795 ms |
553144 KB |
Output is correct |
4 |
Correct |
1815 ms |
553348 KB |
Output is correct |
5 |
Correct |
1684 ms |
495668 KB |
Output is correct |
6 |
Correct |
789 ms |
267600 KB |
Output is correct |
7 |
Correct |
421 ms |
140440 KB |
Output is correct |
8 |
Correct |
69 ms |
28896 KB |
Output is correct |
9 |
Correct |
1763 ms |
502172 KB |
Output is correct |
10 |
Correct |
1567 ms |
519472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1659 ms |
506748 KB |
Output is correct |
2 |
Correct |
1602 ms |
483360 KB |
Output is correct |
3 |
Correct |
1504 ms |
507740 KB |
Output is correct |
4 |
Correct |
1639 ms |
522168 KB |
Output is correct |
5 |
Correct |
1552 ms |
504372 KB |
Output is correct |
6 |
Correct |
1425 ms |
498908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Incorrect |
1 ms |
428 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Incorrect |
1 ms |
428 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |