# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
99818 | TadijaSebez | Circle selection (APIO18_circle_selection) | C++11 | 3095 ms | 93740 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);}
const int N=300050;
circle a[N];
int ans[N];
map<pair<int,int>,vector<circle>> all;
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;
all.clear();
for(i=1;i<=n;i++) if(!ans[a[i].id])
{
all[mp(floor((double)a[i].x/po),floor((double)a[i].y/po))].pb(a[i]);
}
for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j))
{
int x=floor((double)a[i].x/po);
int y=floor((double)a[i].y/po);
for(int l=-2;l<=2;l++) for(int r=-2;r<=2;r++)
{
vector<circle> v=all[mp(x+l,y+r)];
for(circle c:v) 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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |