#include<bits/stdc++.h>
using namespace std;
#define _ int v, int tl, int tr, int l, int r, ll x
#define tm (tl + tr >> 1)
#define sol v+v,tl,tm,l,r,x
#define sag v+v+1,tm+1,tr,l,r,x
#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 p[2],id;
node *l, *r;
node(int a[], int i) { l = r = NULL; p[0] = a[0]; p[1] = a[1]; id = i; }
};
int p[N][2],A[N],B[N],tmp[N],H[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;
node *root = new node(p[ X[m] ] , X[m]);
for(i=l;i<m;i++) H[ X[i] ] = 1;
for(j=l-1,jj=m,i=l;i<=r;i++){
if(H[ Y[i] ])
tmp[++j] = Y[i];
else if(Y[i] != X[m])
tmp[++jj] = Y[i];
}
for(i=l;i<=r;i++) { H[ X[i] ] = 0; Y[i] = tmp[i]; }
root -> l = bld(l,m-1,!k);
root -> r = bld(m+1,r,!k);
return root;
}
int ii;
void f(node* root, int p[], int k){
if(root == NULL) return;
ll a1 = root->p[0];
ll b1 = root->p[1];
ll a2 = p[0];
ll b2 = p[1];
ll c = R[ root->id ];
if((a1-a2)*(a1-a2) + (b1-b2)*(b1-b2) <= (r+c)*(r+c) && !ans[ root->id ])
ans[ root->id ] = ii;
if(p[k] < root->p[k]){
f(root->l,p,!k);
if(root->p[k] - p[k] <= r+r) f(root->r,p,!k);
}
else{
f(root->r,p,!k);
if(p[k] - root->p[k] <= r+r) f(root->l,p,!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;
r = R[id]; ii = id;
f(root , p[id], 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:30: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:75: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; }
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
2 ms |
592 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
3 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
724 KB |
Output is correct |
15 |
Correct |
2 ms |
724 KB |
Output is correct |
16 |
Correct |
3 ms |
724 KB |
Output is correct |
17 |
Correct |
3 ms |
748 KB |
Output is correct |
18 |
Correct |
3 ms |
748 KB |
Output is correct |
19 |
Correct |
10 ms |
1004 KB |
Output is correct |
20 |
Correct |
9 ms |
1132 KB |
Output is correct |
21 |
Correct |
7 ms |
1132 KB |
Output is correct |
22 |
Correct |
8 ms |
1132 KB |
Output is correct |
23 |
Correct |
8 ms |
1164 KB |
Output is correct |
24 |
Correct |
9 ms |
1164 KB |
Output is correct |
25 |
Correct |
9 ms |
1184 KB |
Output is correct |
26 |
Correct |
9 ms |
1184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
424 ms |
28544 KB |
Output is correct |
2 |
Correct |
396 ms |
28560 KB |
Output is correct |
3 |
Correct |
405 ms |
28560 KB |
Output is correct |
4 |
Correct |
496 ms |
28560 KB |
Output is correct |
5 |
Correct |
879 ms |
28560 KB |
Output is correct |
6 |
Execution timed out |
3041 ms |
28560 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
28560 KB |
Output is correct |
2 |
Correct |
189 ms |
28560 KB |
Output is correct |
3 |
Correct |
752 ms |
28560 KB |
Output is correct |
4 |
Correct |
907 ms |
28560 KB |
Output is correct |
5 |
Correct |
661 ms |
28560 KB |
Output is correct |
6 |
Correct |
294 ms |
28560 KB |
Output is correct |
7 |
Correct |
133 ms |
28560 KB |
Output is correct |
8 |
Correct |
26 ms |
28560 KB |
Output is correct |
9 |
Correct |
876 ms |
28560 KB |
Output is correct |
10 |
Correct |
732 ms |
28560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
676 ms |
28560 KB |
Output is correct |
2 |
Correct |
730 ms |
28560 KB |
Output is correct |
3 |
Correct |
561 ms |
28560 KB |
Output is correct |
4 |
Correct |
662 ms |
28560 KB |
Output is correct |
5 |
Correct |
601 ms |
28560 KB |
Output is correct |
6 |
Correct |
528 ms |
28560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
2 ms |
592 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
3 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
724 KB |
Output is correct |
15 |
Correct |
2 ms |
724 KB |
Output is correct |
16 |
Correct |
3 ms |
724 KB |
Output is correct |
17 |
Correct |
3 ms |
748 KB |
Output is correct |
18 |
Correct |
3 ms |
748 KB |
Output is correct |
19 |
Correct |
10 ms |
1004 KB |
Output is correct |
20 |
Correct |
9 ms |
1132 KB |
Output is correct |
21 |
Correct |
7 ms |
1132 KB |
Output is correct |
22 |
Correct |
8 ms |
1132 KB |
Output is correct |
23 |
Correct |
8 ms |
1164 KB |
Output is correct |
24 |
Correct |
9 ms |
1164 KB |
Output is correct |
25 |
Correct |
9 ms |
1184 KB |
Output is correct |
26 |
Correct |
9 ms |
1184 KB |
Output is correct |
27 |
Correct |
15 ms |
28560 KB |
Output is correct |
28 |
Correct |
13 ms |
28560 KB |
Output is correct |
29 |
Correct |
14 ms |
28560 KB |
Output is correct |
30 |
Correct |
17 ms |
28560 KB |
Output is correct |
31 |
Correct |
16 ms |
28560 KB |
Output is correct |
32 |
Correct |
17 ms |
28560 KB |
Output is correct |
33 |
Correct |
157 ms |
28560 KB |
Output is correct |
34 |
Correct |
165 ms |
28560 KB |
Output is correct |
35 |
Correct |
170 ms |
28560 KB |
Output is correct |
36 |
Correct |
227 ms |
28560 KB |
Output is correct |
37 |
Correct |
217 ms |
28560 KB |
Output is correct |
38 |
Correct |
215 ms |
28560 KB |
Output is correct |
39 |
Correct |
329 ms |
28560 KB |
Output is correct |
40 |
Correct |
439 ms |
28560 KB |
Output is correct |
41 |
Correct |
336 ms |
28560 KB |
Output is correct |
42 |
Correct |
172 ms |
28560 KB |
Output is correct |
43 |
Correct |
207 ms |
28560 KB |
Output is correct |
44 |
Correct |
162 ms |
28560 KB |
Output is correct |
45 |
Correct |
167 ms |
28560 KB |
Output is correct |
46 |
Correct |
190 ms |
28560 KB |
Output is correct |
47 |
Correct |
221 ms |
28560 KB |
Output is correct |
48 |
Correct |
181 ms |
28560 KB |
Output is correct |
49 |
Correct |
193 ms |
28560 KB |
Output is correct |
50 |
Correct |
187 ms |
28560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
488 KB |
Output is correct |
3 |
Correct |
2 ms |
488 KB |
Output is correct |
4 |
Correct |
2 ms |
488 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
2 ms |
592 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
3 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
2 ms |
724 KB |
Output is correct |
14 |
Correct |
2 ms |
724 KB |
Output is correct |
15 |
Correct |
2 ms |
724 KB |
Output is correct |
16 |
Correct |
3 ms |
724 KB |
Output is correct |
17 |
Correct |
3 ms |
748 KB |
Output is correct |
18 |
Correct |
3 ms |
748 KB |
Output is correct |
19 |
Correct |
10 ms |
1004 KB |
Output is correct |
20 |
Correct |
9 ms |
1132 KB |
Output is correct |
21 |
Correct |
7 ms |
1132 KB |
Output is correct |
22 |
Correct |
8 ms |
1132 KB |
Output is correct |
23 |
Correct |
8 ms |
1164 KB |
Output is correct |
24 |
Correct |
9 ms |
1164 KB |
Output is correct |
25 |
Correct |
9 ms |
1184 KB |
Output is correct |
26 |
Correct |
9 ms |
1184 KB |
Output is correct |
27 |
Correct |
424 ms |
28544 KB |
Output is correct |
28 |
Correct |
396 ms |
28560 KB |
Output is correct |
29 |
Correct |
405 ms |
28560 KB |
Output is correct |
30 |
Correct |
496 ms |
28560 KB |
Output is correct |
31 |
Correct |
879 ms |
28560 KB |
Output is correct |
32 |
Execution timed out |
3041 ms |
28560 KB |
Time limit exceeded |
33 |
Halted |
0 ms |
0 KB |
- |