Submission #110197

#	Time	Username	Problem	Language	Result	Execution time	Memory
110197		baluteshih	Circle selection (APIO18_circle_selection)	C++14	23 / 100	804 ms	57104 KiB

circle_selection

#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],rmlog,n;
vector<vector<ll>> v;
const ll C=1e9;
 
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]);
}

void split()
{
	--rmlog;
	vector<vector<ll>> tmp;
	for(auto &tv:v)
	{
		vector<ll> sp[2];
		for(auto &i:tv)
			if(!ans[i])
				sp[x[i]>>rmlog&1].pb(i);
		if(sp[0].size()) tmp.pb(sp[0]);
		if(sp[1].size()) tmp.pb(sp[1]);
	}
	v.swap(tmp);
}
 
int main()
{jizz
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> x[i] >> y[i] >> r[i],x[i]+=C,y[i]+=C,arr2[i]=arr[i]=i,rmlog=max(rmlog,__lg(r[i])+1);
	sort(arr+1,arr+n+1,[&](ll a,ll b){return x[a]>>rmlog==x[b]>>rmlog?y[a]<y[b]:x[a]>>rmlog<x[b]>>rmlog;});
	sort(arr2+1,arr2+n+1,[&](ll a,ll b){return r[a]==r[b]?a<b:r[a]>r[b];});
	for(int i=1;i<=n;++i)
		if(v.empty()||x[v.back()[0]]>>rmlog!=x[arr[i]]>>rmlog)
			v.pb(vector<ll>(1,arr[i]));
		else
			v.back().pb(arr[i]);
	for(int i=1;i<=n;++i)
	{
		int cur=arr2[i],L=0,R=v.size();
		if(ans[cur]) continue;
		while(r[cur]<<1<=1<<rmlog)
			split();
		while(L<R)
		{
			int m=L+R>>1;
			if((x[v[m][0]]>>rmlog)+2>=x[cur]>>rmlog) R=m;
			else L=m+1;
		}
		for(int j=L;j<v.size()&&x[v[j][0]]>>rmlog<=(x[cur]>>rmlog)+2;++j)
		{
			int lf=0,ri=v[j].size();
			while(lf<ri)
			{
				int m=lf+ri>>1;
				if(y[v[j][m]]>=y[cur]-r[cur]*2) ri=m;
				else lf=m+1;
			}
			for(int k=lf;k<v[j].size()&&y[v[j][k]]<=y[cur]+r[cur]*2;++k)
				if(!ans[v[j][k]]&&intersect(v[j][k],cur))
					ans[v[j][k]]=cur;
		} 
	}
	for(int i=1;i<=n;++i)
		cout << ans[i] << " \n"[i==n];
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:62:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m=L+R>>1;
          ~^~
circle_selection.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=L;j<v.size()&&x[v[j][0]]>>rmlog<=(x[cur]>>rmlog)+2;++j)
               ~^~~~~~~~~
circle_selection.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=lf+ri>>1;
           ~~^~~
circle_selection.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=lf;k<v[j].size()&&y[v[j][k]]<=y[cur]+r[cur]*2;++k)
                 ~^~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13