#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
struct node{
int id, mn[2];
node *l, *r;
node(int i) { l = r = NULL; id = i; }
};
int p[N][2],A[N],B[N],tmp[N],R[N],ans[N],r;
node* bld(int l, int r, int k){
if(l > r) return NULL;
int *X = k ? B : A;
int *Y = k ? A : B;
int i,j,jj, m = l+r >> 1;
int mid = p[ X[m] ][k];
for(; m>l && mid == p[ X[m-1] ][k] ; m--);
node *root = new node(X[m]);
root->mn[0] = A[l];
root->mn[1] = B[l];
for(j=l-1,jj=m,i=l;i<=r;i++){
if(p[ Y[i] ][k] < mid)
tmp[++j] = Y[i];
else if(Y[i] != X[m])
tmp[++jj] = Y[i];
}
for(i=l;i<=r;i++) Y[i] = tmp[i];
root -> l = bld(l,m-1,!k);
root -> r = bld(m+1,r,!k);
return root;
}
node* del(node* root, int i, int k){
if(root == NULL) assert(0);
if(root->id == i){
if(root -> r != NULL){
int j = root->r->mn[k];
root->id = j;
root->r = del(root->r, j, !k);
}
else if(root -> l != NULL){
int j = root->l->mn[k];
root->id = j; root->r = root->l; root->l = NULL;
root->r = del(root->r, j, !k);
}
else return NULL;
}
else{
if(p[i][k] < p[ root->id ][k]) root->l = del(root->l, i, !k);
else root->r = del(root->r, i, !k);
}
root->mn[k] = root->l ? root->l->mn[k] : root->id;
root->mn[!k] = root->id;
if(root->l != NULL && p[ root->l->mn[!k] ][!k] < p[ root->mn[!k] ][!k]) root->mn[!k] = root->l->mn[!k];
if(root->r != NULL && p[ root->r->mn[!k] ][!k] < p[ root->mn[!k] ][!k]) root->mn[!k] = root->r->mn[!k];
return root;
}
vector < int > era;
void f(node* root, int q[], int k){
if(root == NULL) return;
ll a = q[0] - p[ root->id ][0];
ll b = q[1] - p[ root->id ][1];
ll c = R[ root->id ];
if(a*a + b*b <= (r+c)*(r+c))
era.pb(root->id);
int t = p[ root->id ][k];
if(q[k] < t){
f(root->l,q,!k);
if(t - q[k] <= r+r) f(root->r,q,!k);
}
else{
f(root->r,q,!k);
if(q[k] - t <= r+r) f(root->l,q,!k);
}
}
int h;
bool cmp(int i, int j){
return p[i][h] < p[j][h];
}
int n,i,j;
pp T[N];
int main()
{
cin >> n;
for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i; }
h=0; sort(A+1,A+n+1,cmp);
h=1; sort(B+1,B+n+1,cmp);
node *root = bld(1,n,0);
for(i=1;i<=n;i++) T[i] = mp(-R[i] , i);
sort(T+1 , T+n+1);
for(i=1;i<=n;i++){
int id = T[i].nd;
if(ans[id]) continue;
era.clear();
r = R[id];
f(root , p[id], 0);
for(auto j : era){
ans[j] = id;
root = del(root, j, 0);
}
}
for(i=1;i<=n;i++) printf("%d ", ans[i]);
return 0;
}
Compilation message
circle_selection.cpp: In function 'node* bld(int, int, int)':
circle_selection.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int i,j,jj, m = l+r >> 1;
~^~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:100:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i; }
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
540 KB |
Output is correct |
4 |
Correct |
2 ms |
628 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
3 ms |
628 KB |
Output is correct |
10 |
Correct |
2 ms |
636 KB |
Output is correct |
11 |
Correct |
2 ms |
636 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
636 KB |
Output is correct |
14 |
Correct |
2 ms |
636 KB |
Output is correct |
15 |
Correct |
2 ms |
636 KB |
Output is correct |
16 |
Correct |
4 ms |
636 KB |
Output is correct |
17 |
Correct |
4 ms |
636 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
9 ms |
1148 KB |
Output is correct |
20 |
Correct |
11 ms |
1148 KB |
Output is correct |
21 |
Correct |
11 ms |
1148 KB |
Output is correct |
22 |
Correct |
11 ms |
1148 KB |
Output is correct |
23 |
Correct |
10 ms |
1148 KB |
Output is correct |
24 |
Correct |
10 ms |
1148 KB |
Output is correct |
25 |
Correct |
11 ms |
1148 KB |
Output is correct |
26 |
Correct |
10 ms |
1148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
555 ms |
28760 KB |
Output is correct |
2 |
Correct |
564 ms |
28760 KB |
Output is correct |
3 |
Correct |
550 ms |
28760 KB |
Output is correct |
4 |
Correct |
634 ms |
28760 KB |
Output is correct |
5 |
Correct |
462 ms |
28760 KB |
Output is correct |
6 |
Correct |
619 ms |
28760 KB |
Output is correct |
7 |
Correct |
651 ms |
28760 KB |
Output is correct |
8 |
Correct |
595 ms |
28760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
28760 KB |
Output is correct |
2 |
Correct |
306 ms |
28760 KB |
Output is correct |
3 |
Correct |
964 ms |
28760 KB |
Output is correct |
4 |
Correct |
1072 ms |
28760 KB |
Output is correct |
5 |
Correct |
913 ms |
28760 KB |
Output is correct |
6 |
Correct |
376 ms |
28760 KB |
Output is correct |
7 |
Correct |
190 ms |
28760 KB |
Output is correct |
8 |
Correct |
29 ms |
28760 KB |
Output is correct |
9 |
Correct |
1081 ms |
28760 KB |
Output is correct |
10 |
Correct |
904 ms |
28760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
812 ms |
28760 KB |
Output is correct |
2 |
Correct |
780 ms |
28760 KB |
Output is correct |
3 |
Correct |
585 ms |
28760 KB |
Output is correct |
4 |
Correct |
909 ms |
28760 KB |
Output is correct |
5 |
Correct |
871 ms |
28760 KB |
Output is correct |
6 |
Correct |
596 ms |
28760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
540 KB |
Output is correct |
4 |
Correct |
2 ms |
628 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
3 ms |
628 KB |
Output is correct |
10 |
Correct |
2 ms |
636 KB |
Output is correct |
11 |
Correct |
2 ms |
636 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
636 KB |
Output is correct |
14 |
Correct |
2 ms |
636 KB |
Output is correct |
15 |
Correct |
2 ms |
636 KB |
Output is correct |
16 |
Correct |
4 ms |
636 KB |
Output is correct |
17 |
Correct |
4 ms |
636 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
9 ms |
1148 KB |
Output is correct |
20 |
Correct |
11 ms |
1148 KB |
Output is correct |
21 |
Correct |
11 ms |
1148 KB |
Output is correct |
22 |
Correct |
11 ms |
1148 KB |
Output is correct |
23 |
Correct |
10 ms |
1148 KB |
Output is correct |
24 |
Correct |
10 ms |
1148 KB |
Output is correct |
25 |
Correct |
11 ms |
1148 KB |
Output is correct |
26 |
Correct |
10 ms |
1148 KB |
Output is correct |
27 |
Correct |
15 ms |
28760 KB |
Output is correct |
28 |
Correct |
15 ms |
28760 KB |
Output is correct |
29 |
Correct |
16 ms |
28760 KB |
Output is correct |
30 |
Correct |
20 ms |
28760 KB |
Output is correct |
31 |
Correct |
20 ms |
28760 KB |
Output is correct |
32 |
Correct |
21 ms |
28760 KB |
Output is correct |
33 |
Correct |
174 ms |
28760 KB |
Output is correct |
34 |
Correct |
173 ms |
28760 KB |
Output is correct |
35 |
Correct |
187 ms |
28760 KB |
Output is correct |
36 |
Correct |
260 ms |
28760 KB |
Output is correct |
37 |
Correct |
214 ms |
28760 KB |
Output is correct |
38 |
Correct |
222 ms |
28760 KB |
Output is correct |
39 |
Correct |
290 ms |
28760 KB |
Output is correct |
40 |
Correct |
278 ms |
28760 KB |
Output is correct |
41 |
Correct |
440 ms |
28760 KB |
Output is correct |
42 |
Correct |
181 ms |
28760 KB |
Output is correct |
43 |
Correct |
247 ms |
28760 KB |
Output is correct |
44 |
Correct |
206 ms |
28760 KB |
Output is correct |
45 |
Correct |
195 ms |
28760 KB |
Output is correct |
46 |
Correct |
177 ms |
28760 KB |
Output is correct |
47 |
Correct |
172 ms |
28760 KB |
Output is correct |
48 |
Correct |
186 ms |
28760 KB |
Output is correct |
49 |
Correct |
196 ms |
28760 KB |
Output is correct |
50 |
Correct |
179 ms |
28760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
540 KB |
Output is correct |
4 |
Correct |
2 ms |
628 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
2 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
3 ms |
628 KB |
Output is correct |
10 |
Correct |
2 ms |
636 KB |
Output is correct |
11 |
Correct |
2 ms |
636 KB |
Output is correct |
12 |
Correct |
2 ms |
636 KB |
Output is correct |
13 |
Correct |
2 ms |
636 KB |
Output is correct |
14 |
Correct |
2 ms |
636 KB |
Output is correct |
15 |
Correct |
2 ms |
636 KB |
Output is correct |
16 |
Correct |
4 ms |
636 KB |
Output is correct |
17 |
Correct |
4 ms |
636 KB |
Output is correct |
18 |
Correct |
3 ms |
636 KB |
Output is correct |
19 |
Correct |
9 ms |
1148 KB |
Output is correct |
20 |
Correct |
11 ms |
1148 KB |
Output is correct |
21 |
Correct |
11 ms |
1148 KB |
Output is correct |
22 |
Correct |
11 ms |
1148 KB |
Output is correct |
23 |
Correct |
10 ms |
1148 KB |
Output is correct |
24 |
Correct |
10 ms |
1148 KB |
Output is correct |
25 |
Correct |
11 ms |
1148 KB |
Output is correct |
26 |
Correct |
10 ms |
1148 KB |
Output is correct |
27 |
Correct |
555 ms |
28760 KB |
Output is correct |
28 |
Correct |
564 ms |
28760 KB |
Output is correct |
29 |
Correct |
550 ms |
28760 KB |
Output is correct |
30 |
Correct |
634 ms |
28760 KB |
Output is correct |
31 |
Correct |
462 ms |
28760 KB |
Output is correct |
32 |
Correct |
619 ms |
28760 KB |
Output is correct |
33 |
Correct |
651 ms |
28760 KB |
Output is correct |
34 |
Correct |
595 ms |
28760 KB |
Output is correct |
35 |
Correct |
2 ms |
28760 KB |
Output is correct |
36 |
Correct |
306 ms |
28760 KB |
Output is correct |
37 |
Correct |
964 ms |
28760 KB |
Output is correct |
38 |
Correct |
1072 ms |
28760 KB |
Output is correct |
39 |
Correct |
913 ms |
28760 KB |
Output is correct |
40 |
Correct |
376 ms |
28760 KB |
Output is correct |
41 |
Correct |
190 ms |
28760 KB |
Output is correct |
42 |
Correct |
29 ms |
28760 KB |
Output is correct |
43 |
Correct |
1081 ms |
28760 KB |
Output is correct |
44 |
Correct |
904 ms |
28760 KB |
Output is correct |
45 |
Correct |
812 ms |
28760 KB |
Output is correct |
46 |
Correct |
780 ms |
28760 KB |
Output is correct |
47 |
Correct |
585 ms |
28760 KB |
Output is correct |
48 |
Correct |
909 ms |
28760 KB |
Output is correct |
49 |
Correct |
871 ms |
28760 KB |
Output is correct |
50 |
Correct |
596 ms |
28760 KB |
Output is correct |
51 |
Correct |
15 ms |
28760 KB |
Output is correct |
52 |
Correct |
15 ms |
28760 KB |
Output is correct |
53 |
Correct |
16 ms |
28760 KB |
Output is correct |
54 |
Correct |
20 ms |
28760 KB |
Output is correct |
55 |
Correct |
20 ms |
28760 KB |
Output is correct |
56 |
Correct |
21 ms |
28760 KB |
Output is correct |
57 |
Correct |
174 ms |
28760 KB |
Output is correct |
58 |
Correct |
173 ms |
28760 KB |
Output is correct |
59 |
Correct |
187 ms |
28760 KB |
Output is correct |
60 |
Correct |
260 ms |
28760 KB |
Output is correct |
61 |
Correct |
214 ms |
28760 KB |
Output is correct |
62 |
Correct |
222 ms |
28760 KB |
Output is correct |
63 |
Correct |
290 ms |
28760 KB |
Output is correct |
64 |
Correct |
278 ms |
28760 KB |
Output is correct |
65 |
Correct |
440 ms |
28760 KB |
Output is correct |
66 |
Correct |
181 ms |
28760 KB |
Output is correct |
67 |
Correct |
247 ms |
28760 KB |
Output is correct |
68 |
Correct |
206 ms |
28760 KB |
Output is correct |
69 |
Correct |
195 ms |
28760 KB |
Output is correct |
70 |
Correct |
177 ms |
28760 KB |
Output is correct |
71 |
Correct |
172 ms |
28760 KB |
Output is correct |
72 |
Correct |
186 ms |
28760 KB |
Output is correct |
73 |
Correct |
196 ms |
28760 KB |
Output is correct |
74 |
Correct |
179 ms |
28760 KB |
Output is correct |
75 |
Correct |
677 ms |
28760 KB |
Output is correct |
76 |
Correct |
587 ms |
28760 KB |
Output is correct |
77 |
Correct |
524 ms |
28760 KB |
Output is correct |
78 |
Correct |
573 ms |
28760 KB |
Output is correct |
79 |
Correct |
587 ms |
28760 KB |
Output is correct |
80 |
Correct |
549 ms |
28760 KB |
Output is correct |
81 |
Correct |
827 ms |
28760 KB |
Output is correct |
82 |
Correct |
831 ms |
28760 KB |
Output is correct |
83 |
Correct |
988 ms |
28760 KB |
Output is correct |
84 |
Correct |
996 ms |
28760 KB |
Output is correct |
85 |
Correct |
999 ms |
28760 KB |
Output is correct |
86 |
Correct |
1057 ms |
28760 KB |
Output is correct |
87 |
Correct |
1037 ms |
28760 KB |
Output is correct |
88 |
Correct |
1867 ms |
28760 KB |
Output is correct |
89 |
Correct |
1844 ms |
28760 KB |
Output is correct |
90 |
Correct |
2055 ms |
28760 KB |
Output is correct |
91 |
Correct |
1942 ms |
28760 KB |
Output is correct |
92 |
Correct |
1892 ms |
28760 KB |
Output is correct |
93 |
Correct |
2264 ms |
28760 KB |
Output is correct |
94 |
Execution timed out |
3052 ms |
28760 KB |
Time limit exceeded |
95 |
Halted |
0 ms |
0 KB |
- |