#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
using ll = long long;
const ll MOD = 1e9+7;
const int MAX_N = 3e5+5;
int n;
struct Node
{
ll x, y, r;
int p;
bool visited;
} A[MAX_N];
struct LLNode
{
int idx;
LLNode* next = nullptr;
inline LLNode()
{
}
inline LLNode(const int & val)
: idx(val)
{
}
} LLNodes[MAX_N];
int llcounter = 0;
inline LLNode* getLLNode()
{
return &LLNodes[llcounter++];
}
int dup;
struct Quad;
inline Quad* getQuadNode();
struct Quad
{
ll l, r, bot, top;
array<Quad*, 4> childs = {};
LLNode* llnode = nullptr;
int sz;
inline Quad()
{
}
inline Quad(const ll & _l, const ll & _r, const ll & _bot, const ll & _top)
: l(_l), r(_r), bot(_bot), top(_top)
{
sz = 0;
}
void add(const ll & x, const ll & y, const 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) {
if(llnode == nullptr) {
llnode = getLLNode();
llnode->idx = idx;
}
else {
dup++;
LLNode* temp = getLLNode();
temp->idx = idx;
temp->next = llnode;
llnode = temp;
}
}
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] = getQuadNode();
childs[0]->l = l;
childs[0]->r = midH;
childs[0]->bot = bot;
childs[0]->top = midV;
}
else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > midV)) {
childs[1] = getQuadNode();
childs[1]->l = midH+1;
childs[1]->r = r;
childs[1]->bot = bot;
childs[1]->top = midV;
}
else if(childs[2] == nullptr && !(x < l || x > midH || y < midV+1 || y > top)) {
childs[2] = getQuadNode();
childs[2]->l = l;
childs[2]->r = midH;
childs[2]->bot = midV+1;
childs[2]->top = top;
}
else if(childs[3] == nullptr && !(x < midH+1 || x > r || y < midV+1 || y > top)) {
childs[3] = getQuadNode();
childs[3]->l = midH+1;
childs[3]->r = r;
childs[3]->bot = midV+1;
childs[3]->top = top;
}
}
else if(l != r) {
if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > top)) {
childs[0] = getQuadNode();
childs[0]->l = l;
childs[0]->r = midH;
childs[0]->bot = bot;
childs[0]->top = top;
}
else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > top)) {
childs[1] = getQuadNode();
childs[1]->l = midH+1;
childs[1]->r = r;
childs[1]->bot = bot;
childs[1]->top = top;
}
}
else if(top != bot) {
if(childs[0] == nullptr && !(x < l || x > r || y < bot || y > midV)) {
childs[0] = getQuadNode();
childs[0]->l = l;
childs[0]->r = r;
childs[0]->bot = bot;
childs[0]->top = midV;
}
else if(childs[1] == nullptr && !(x < l || x > r || y < midV+1 || y > top)) {
childs[1] = getQuadNode();
childs[1]->l = l;
childs[1]->r = r;
childs[1]->bot = midV+1;
childs[1]->top = top;
}
}
for(int k = 0; k < 4; k++) {
if(childs[k] != nullptr) {
childs[k]->add(x, y, idx);
}
}
}
}
void setInRange(const ll & x, const ll & y, const ll & radius, const 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) {
while(llnode != nullptr &&
(A[idx].r+A[llnode->idx].r)*(A[idx].r+A[llnode->idx].r)
>= llabs(A[idx].x-A[llnode->idx].x)*llabs(A[idx].x-A[llnode->idx].x)
+llabs(A[idx].y-A[llnode->idx].y)*llabs(A[idx].y-A[llnode->idx].y)) {
A[llnode->idx].p = idx;
A[llnode->idx].visited = true;
sz--;
llnode = llnode->next;
}
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;
}
} QuadNodes[MAX_N*50];
int quadcounter = 0;
inline Quad* getQuadNode()
{
return &QuadNodes[quadcounter++];
}
Quad Q(-1000000000, 1000000000, -1000000000, 1000000000);
inline int nextInt()
{
int c = getchar();
while (c != '-' && (c < '0' || c > '9')) {
c = getchar();
}
int x = 0;
bool neg = false;
if (c == '-') {
neg = true;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x*10+(c-'0');
c = getchar();
}
if (neg)
return -x;
return x;
}
int main()
{
auto stop = steady_clock::now();
n = nextInt();
for(int i = 0; i < n; i++) {
A[i].x = nextInt();
A[i].y = nextInt();
A[i].r = nextInt();
}
//cerr << "Exec: " << duration_cast<milliseconds>(steady_clock::now()-stop).count() << " ms\n";
vector<int> I(n);
iota(I.begin(), I.end(), 0);
sort(I.begin(), I.end(),
[&](int a, int b)
{
return A[a].r > A[b].r || (A[a].r == A[b].r && a < b);
});
for(int i = n-1; i >= 0; i--) {
int idx = I[i];
//cerr << i << " started\n";
Q.add(A[idx].x, A[idx].y, idx);
//cerr << i << " finished\n";
}
for(int i = 0; i < n; i++) {
int idx = I[i];
if(A[idx].visited) continue;
Q.setInRange(A[idx].x, A[idx].y, A[idx].r, idx);
}
for(int i = 0; i < n; i++) {
cout << 1+A[i].p << " ";
}
cout << "\n";
//cerr << "Dupe: " << dup << "\n";
//cerr << "Exec: " << duration_cast<milliseconds>(steady_clock::now()-stop).count() << " ms\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
*/
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:223:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
223 | auto stop = steady_clock::now();
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
346 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
362 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
353 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
347 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
