#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
struct circle{ ll x,y,r;int id;circle(){}circle(ll a, ll b, ll c):x(a),y(b),r(c){}};
ll sq(ll x){ return x*x;}
bool sec(circle a, circle b){ return sq(a.x-b.x)+sq(a.y-b.y)<=sq(a.r+b.r);}
bool operator < (circle a, circle b){ return a.r<b.r;}
const int N=300050;
const int mul=2e9+7;
circle a[N],b[N];
int ans[N];
unordered_map<ll,int> id;
vector<pair<int,int>> all[N];
int main()
{
int n,i;
scanf("%i",&n);
for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i,b[i]=a[i];
sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
for(int j=30;j>=0;j--)
{
int po=1<<j;
id.clear();
int cnt=0;
for(i=1;i<=n;i++) if(!ans[a[i].id])
{
pair<int,int> pa=mp(floor((double)a[i].x/po),floor((double)a[i].y/po));
ll p=pa.first;
if(!id[p]) id[p]=++cnt,all[cnt].clear();
all[id[p]].pb(mp(pa.second,a[i].id));
}
for(i=1;i<=cnt;i++) sort(all[i].begin(),all[i].end());
for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
{
int x=floor((double)a[i].x/po);
int y=floor((double)a[i].y/po);
for(int l=-2;l<=2;l++)
{
ll p=x+l;
if(!id.count(p)) continue;
int idx=id[p];
int lb=upper_bound(all[idx].begin(),all[idx].end(),mp(y-3,mul))-all[idx].begin();
int rb=upper_bound(all[idx].begin(),all[idx].end(),mp(y+2,mul))-all[idx].begin();
for(int r=lb;r<rb;r++)
{
int c=all[idx][r].second;
if(!ans[c] && sec(b[c],a[i])) ans[c]=a[i].id;
}
}
}
}
for(i=1;i<=n;i++) printf("%i%c",ans[i],i==n?'\n':' ');
return 0;
}
Compilation message
circle_selection.cpp: In lambda function:
circle_selection.cpp:21:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
~~~~~~~~~^~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:35:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
~^~
circle_selection.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
circle_selection.cpp:20:77: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i,b[i]=a[i];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
9 ms |
7424 KB |
Output is correct |
5 |
Correct |
8 ms |
7424 KB |
Output is correct |
6 |
Correct |
11 ms |
7424 KB |
Output is correct |
7 |
Correct |
9 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
9 ms |
7424 KB |
Output is correct |
13 |
Correct |
8 ms |
7424 KB |
Output is correct |
14 |
Correct |
8 ms |
7424 KB |
Output is correct |
15 |
Correct |
9 ms |
7424 KB |
Output is correct |
16 |
Correct |
9 ms |
7424 KB |
Output is correct |
17 |
Correct |
11 ms |
7552 KB |
Output is correct |
18 |
Correct |
12 ms |
7424 KB |
Output is correct |
19 |
Correct |
14 ms |
7852 KB |
Output is correct |
20 |
Correct |
14 ms |
7808 KB |
Output is correct |
21 |
Correct |
14 ms |
7808 KB |
Output is correct |
22 |
Correct |
22 ms |
8320 KB |
Output is correct |
23 |
Correct |
23 ms |
8064 KB |
Output is correct |
24 |
Correct |
33 ms |
8320 KB |
Output is correct |
25 |
Correct |
29 ms |
8312 KB |
Output is correct |
26 |
Correct |
30 ms |
8320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
408 ms |
32212 KB |
Output is correct |
2 |
Correct |
480 ms |
34308 KB |
Output is correct |
3 |
Correct |
470 ms |
32964 KB |
Output is correct |
4 |
Correct |
453 ms |
32884 KB |
Output is correct |
5 |
Correct |
1056 ms |
48608 KB |
Output is correct |
6 |
Correct |
1541 ms |
65880 KB |
Output is correct |
7 |
Correct |
1024 ms |
51848 KB |
Output is correct |
8 |
Correct |
1116 ms |
59740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7424 KB |
Output is correct |
2 |
Correct |
400 ms |
21984 KB |
Output is correct |
3 |
Correct |
1523 ms |
56708 KB |
Output is correct |
4 |
Correct |
1522 ms |
57868 KB |
Output is correct |
5 |
Correct |
1241 ms |
51036 KB |
Output is correct |
6 |
Correct |
672 ms |
30496 KB |
Output is correct |
7 |
Correct |
265 ms |
19948 KB |
Output is correct |
8 |
Correct |
62 ms |
10360 KB |
Output is correct |
9 |
Correct |
1417 ms |
54828 KB |
Output is correct |
10 |
Correct |
1130 ms |
47224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1659 ms |
56556 KB |
Output is correct |
2 |
Execution timed out |
3052 ms |
74924 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
9 ms |
7424 KB |
Output is correct |
5 |
Correct |
8 ms |
7424 KB |
Output is correct |
6 |
Correct |
11 ms |
7424 KB |
Output is correct |
7 |
Correct |
9 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
9 ms |
7424 KB |
Output is correct |
13 |
Correct |
8 ms |
7424 KB |
Output is correct |
14 |
Correct |
8 ms |
7424 KB |
Output is correct |
15 |
Correct |
9 ms |
7424 KB |
Output is correct |
16 |
Correct |
9 ms |
7424 KB |
Output is correct |
17 |
Correct |
11 ms |
7552 KB |
Output is correct |
18 |
Correct |
12 ms |
7424 KB |
Output is correct |
19 |
Correct |
14 ms |
7852 KB |
Output is correct |
20 |
Correct |
14 ms |
7808 KB |
Output is correct |
21 |
Correct |
14 ms |
7808 KB |
Output is correct |
22 |
Correct |
22 ms |
8320 KB |
Output is correct |
23 |
Correct |
23 ms |
8064 KB |
Output is correct |
24 |
Correct |
33 ms |
8320 KB |
Output is correct |
25 |
Correct |
29 ms |
8312 KB |
Output is correct |
26 |
Correct |
30 ms |
8320 KB |
Output is correct |
27 |
Correct |
19 ms |
8320 KB |
Output is correct |
28 |
Correct |
20 ms |
8292 KB |
Output is correct |
29 |
Correct |
18 ms |
8320 KB |
Output is correct |
30 |
Correct |
43 ms |
8952 KB |
Output is correct |
31 |
Correct |
42 ms |
9208 KB |
Output is correct |
32 |
Correct |
38 ms |
9116 KB |
Output is correct |
33 |
Correct |
113 ms |
15580 KB |
Output is correct |
34 |
Correct |
108 ms |
15592 KB |
Output is correct |
35 |
Correct |
136 ms |
16036 KB |
Output is correct |
36 |
Correct |
429 ms |
25808 KB |
Output is correct |
37 |
Correct |
408 ms |
25412 KB |
Output is correct |
38 |
Correct |
376 ms |
23884 KB |
Output is correct |
39 |
Correct |
585 ms |
19392 KB |
Output is correct |
40 |
Correct |
507 ms |
19864 KB |
Output is correct |
41 |
Correct |
550 ms |
19348 KB |
Output is correct |
42 |
Correct |
350 ms |
19220 KB |
Output is correct |
43 |
Correct |
506 ms |
29596 KB |
Output is correct |
44 |
Correct |
591 ms |
30156 KB |
Output is correct |
45 |
Correct |
667 ms |
29596 KB |
Output is correct |
46 |
Correct |
601 ms |
29644 KB |
Output is correct |
47 |
Correct |
553 ms |
29816 KB |
Output is correct |
48 |
Correct |
610 ms |
29728 KB |
Output is correct |
49 |
Correct |
634 ms |
29996 KB |
Output is correct |
50 |
Correct |
642 ms |
29636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7424 KB |
Output is correct |
2 |
Correct |
10 ms |
7424 KB |
Output is correct |
3 |
Correct |
9 ms |
7424 KB |
Output is correct |
4 |
Correct |
9 ms |
7424 KB |
Output is correct |
5 |
Correct |
8 ms |
7424 KB |
Output is correct |
6 |
Correct |
11 ms |
7424 KB |
Output is correct |
7 |
Correct |
9 ms |
7424 KB |
Output is correct |
8 |
Correct |
9 ms |
7424 KB |
Output is correct |
9 |
Correct |
8 ms |
7424 KB |
Output is correct |
10 |
Correct |
9 ms |
7424 KB |
Output is correct |
11 |
Correct |
9 ms |
7424 KB |
Output is correct |
12 |
Correct |
9 ms |
7424 KB |
Output is correct |
13 |
Correct |
8 ms |
7424 KB |
Output is correct |
14 |
Correct |
8 ms |
7424 KB |
Output is correct |
15 |
Correct |
9 ms |
7424 KB |
Output is correct |
16 |
Correct |
9 ms |
7424 KB |
Output is correct |
17 |
Correct |
11 ms |
7552 KB |
Output is correct |
18 |
Correct |
12 ms |
7424 KB |
Output is correct |
19 |
Correct |
14 ms |
7852 KB |
Output is correct |
20 |
Correct |
14 ms |
7808 KB |
Output is correct |
21 |
Correct |
14 ms |
7808 KB |
Output is correct |
22 |
Correct |
22 ms |
8320 KB |
Output is correct |
23 |
Correct |
23 ms |
8064 KB |
Output is correct |
24 |
Correct |
33 ms |
8320 KB |
Output is correct |
25 |
Correct |
29 ms |
8312 KB |
Output is correct |
26 |
Correct |
30 ms |
8320 KB |
Output is correct |
27 |
Correct |
408 ms |
32212 KB |
Output is correct |
28 |
Correct |
480 ms |
34308 KB |
Output is correct |
29 |
Correct |
470 ms |
32964 KB |
Output is correct |
30 |
Correct |
453 ms |
32884 KB |
Output is correct |
31 |
Correct |
1056 ms |
48608 KB |
Output is correct |
32 |
Correct |
1541 ms |
65880 KB |
Output is correct |
33 |
Correct |
1024 ms |
51848 KB |
Output is correct |
34 |
Correct |
1116 ms |
59740 KB |
Output is correct |
35 |
Correct |
9 ms |
7424 KB |
Output is correct |
36 |
Correct |
400 ms |
21984 KB |
Output is correct |
37 |
Correct |
1523 ms |
56708 KB |
Output is correct |
38 |
Correct |
1522 ms |
57868 KB |
Output is correct |
39 |
Correct |
1241 ms |
51036 KB |
Output is correct |
40 |
Correct |
672 ms |
30496 KB |
Output is correct |
41 |
Correct |
265 ms |
19948 KB |
Output is correct |
42 |
Correct |
62 ms |
10360 KB |
Output is correct |
43 |
Correct |
1417 ms |
54828 KB |
Output is correct |
44 |
Correct |
1130 ms |
47224 KB |
Output is correct |
45 |
Correct |
1659 ms |
56556 KB |
Output is correct |
46 |
Execution timed out |
3052 ms |
74924 KB |
Time limit exceeded |
47 |
Halted |
0 ms |
0 KB |
- |