#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 1;}
const int N=300050;
const ll mul=2e9+7;
circle a[N];
int ans[N];
unordered_map<ll,int> id;
vector<pair<int,circle>> 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;
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]));
}
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,a[i]))-all[idx].begin();
int rb=upper_bound(all[idx].begin(),all[idx].end(),mp(y+2,a[i]))-all[idx].begin();
for(int r=lb;r<rb;r++)
{
if(r<0 || r>=all[idx].size()) continue;
circle c=all[idx][r].second;
if(c.id<=0 || c.id>n) continue;
if(!ans[c.id] && sec(c,a[i])) ans[c.id]=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:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(r<0 || r>=all[idx].size()) continue;
~^~~~~~~~~~~~~~~~~
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:67: 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;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 6 |
Runtime error |
18 ms |
14592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
242 ms |
57360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Runtime error |
96 ms |
28944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
233 ms |
57188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 6 |
Runtime error |
18 ms |
14592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 5 |
Correct |
8 ms |
7424 KB |
Output is correct |
| 6 |
Runtime error |
18 ms |
14592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
