#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll ans[300005],x[300005],y[300005],r[300005],arr[300005],arr2[300005],rmax,n;
vector<vector<vector<ll>>> v;
vector<vector<ll>> sigy;
vector<ll> sigx;
bool yee(ll a,ll b)
{
if(x[a]==x[b]) return y[a]<y[b];
return x[a]<x[b];
}
bool yee2(ll a,ll b)
{
if(r[a]==r[b]) return a<b;
return r[a]>r[b];
}
bool intersect(ll a,ll b)
{
return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])<=(r[a]+r[b])*(r[a]+r[b]);
}
ll blk(ll x)
{
if(x>0) return x/rmax;
return x/rmax-1;
}
void rebuild()
{
vector<vector<vector<ll>>>().swap(v);
vector<ll>().swap(sigx),vector<vector<ll>>().swap(sigy);
for(int i=1;i<=n;++i)
if(!ans[arr[i]])
if(v.empty()||sigx.back()!=blk(x[arr[i]]))
v.pb(vector<vector<ll>>(1,vector<ll>(1,arr[i]))),sigx.pb(blk(x[arr[i]])),sigy.pb(vector<ll>(1,blk(y[arr[i]])));
else
if(sigy.back().back()==blk(y[arr[i]])) v.back().back().pb(arr[i]);
else v.back().pb(vector<ll>(1,arr[i])),sigy.back().pb(blk(y[arr[i]]));
}
int main()
{jizz
cin >> n;
for(int i=1;i<=n;++i)
cin >> x[i] >> y[i] >> r[i],arr2[i]=arr[i]=i,rmax=max(rmax,r[i]);
sort(arr+1,arr+n+1,yee),sort(arr2+1,arr2+n+1,yee2),rebuild();
for(int i=1;i<=n;++i)
{
int cur=arr2[i];
if(ans[cur]) continue;
if(r[cur]*2<=rmax)
rmax=r[cur],rebuild();
int L=0,R=v.size();
while(L<R)
{
int m=L+R>>1;
if(sigx[m]+2>=blk(x[cur])) R=m;
else L=m+1;
}
for(int j=L;j<v.size()&&sigx[j]<=blk(x[cur])+2;++j)
{
int l=0,r=v[j].size();
while(l<r)
{
int m=l+r>>1;
if(sigy[j][m]+2>=blk(y[cur])) r=m;
else l=m+1;
}
for(int k=l;k<v[j].size()&&sigy[j][k]<=blk(y[cur])+2;++k)
{
vector<ll> tmp;
for(auto p:v[j][k])
if(intersect(p,cur)) ans[p]=cur;
else tmp.pb(p);
v[j][k].swap(tmp);
}
}
}
for(int i=1;i<=n;++i)
cout << ans[i] << " \n"[i==n];
}
Compilation message
circle_selection.cpp: In function 'void rebuild()':
circle_selection.cpp:50:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(!ans[arr[i]])
^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:73:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=L+R>>1;
~^~
circle_selection.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=L;j<v.size()&&sigx[j]<=blk(x[cur])+2;++j)
~^~~~~~~~~
circle_selection.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
circle_selection.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=l;k<v[j].size()&&sigy[j][k]<=blk(y[cur])+2;++k)
~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
18772 KB |
Output is correct |
2 |
Correct |
284 ms |
17660 KB |
Output is correct |
3 |
Correct |
289 ms |
17776 KB |
Output is correct |
4 |
Correct |
321 ms |
16996 KB |
Output is correct |
5 |
Correct |
339 ms |
18808 KB |
Output is correct |
6 |
Correct |
698 ms |
37308 KB |
Output is correct |
7 |
Correct |
403 ms |
20328 KB |
Output is correct |
8 |
Correct |
472 ms |
23516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
899 ms |
43760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |