#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int n;
i4 arr[300005];
int X[300005],Y[300005],R[300005];
int proc=0;
int ans[300005];
int scale=(1<<30);
map<ii,vector<int> > m;
inline void downscale(){
m.clear();
for(int x=proc;x<n;x++){
i4 i=arr[x];
if(ans[-i.fi.se]==-1)m[mp(i.se.fi/scale,i.se.se/scale)].pb(-i.fi.se);
}
}
inline bool intersect(int a,int b){
ll dx=X[a]-X[b];
ll dy=Y[a]-Y[b];
ll r=R[a]+R[b];
return (dx*dx<=r*r-dy*dy);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d",&X[i],&Y[i],&R[i]);
X[i]+=MOD;Y[i]+=MOD;
arr[i]=mp(mp(R[i],-i),mp(X[i],Y[i]));
}
memset(ans,-1,sizeof(ans));
sort(arr,arr+n);
reverse(arr,arr+n);
downscale();
for(;proc<n;proc++){
i4 cur=arr[proc];
int index=-cur.fi.se;
if(ans[index]!=-1)continue;
ans[index]=index;
bool change=0;
while(scale>cur.fi.fi){scale/=2;change=1;}
if(change)downscale();
int x=cur.se.fi/scale,y=cur.se.se/scale;
for(int i=x-2;i<=x+2;i++){
for(int j=y-2;j<=y+2;j++){
vector<int> v1=m[mp(i,j)];
vector<int> v2;
for(int k:v1){
if(intersect(k,index)){
ans[k]=index;
}else{
v2.pb(k);
}
}
swap(m[mp(i,j)],v2);
}
}
}
for(int i=0;i<n;i++)printf("%d ",ans[i]+1);
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
circle_selection.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%d%d",&X[i],&Y[i],&R[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1588 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
131 ms |
13572 KB |
Output is correct |
| 2 |
Incorrect |
138 ms |
13496 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Incorrect |
1377 ms |
89260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3075 ms |
537152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1588 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1588 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
