Submission #99818

#TimeUsernameProblemLanguageResultExecution timeMemory
99818TadijaSebezCircle selection (APIO18_circle_selection)C++11
0 / 100
3095 ms93740 KiB
#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)

circle_selection.cpp: In lambda function:
circle_selection.cpp:18: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:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:17: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...