Submission #64376

#	Time	Username	Problem	Language	Result	Execution time	Memory
64376		zscoder	Circle selection (APIO18_circle_selection)	C++17	100 / 100	2671 ms	387520 KiB

circle_selection

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct circle
{
	int x,y,r,id;
	circle(int _x, int _y, int _r, int _id){x=_x;y=_y;r=_r;id=_id;}
};

bool operator<(circle a, circle b)
{
	if(a.r!=b.r) return a.r<b.r;
	else return a.id>b.id;
}

bool cmp(circle a, circle b)
{
	if(a.y!=b.y) return a.y<b.y;
	else return a.id>b.id;
}
vector<circle> a;
int ans[333333];
vector<circle> vec;

vector<pair<int,int> > V[333333];
vi xs;
vector<circle> v2;

void init(int R)
{
	xs.clear();
	for(int i=0;i<vec.size();i++)
	{
		if(!ans[vec[i].id])
		{
			xs.pb(vec[i].x/R);
		}
	}
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for(int i=0;i<xs.size();i++) V[i].clear();
	for(int i=0;i<v2.size();i++)
	{
		if(!ans[v2[i].id])
		{
			V[lower_bound(xs.begin(),xs.end(),v2[i].x/R)-xs.begin()].pb(mp(v2[i].y/R, v2[i].id));
		}
	}
}

bool intersect(circle x, circle y)
{
	ll d = (x.x-y.x)*1LL*(x.x-y.x) + (x.y-y.y)*1LL*(x.y-y.y);
	return (d<=(x.r+y.r)*1LL*(x.r+y.r));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		int x,y,r; cin>>x>>y>>r;
		vec.pb(circle(x,y,r,i+1));
	}
	a=vec; v2=vec;
	sort(v2.begin(),v2.end(),cmp);
	sort(vec.rbegin(),vec.rend());
	int curC = int(1e9); init(curC);
	for(int i=0;i<vec.size();i++)
	{
		if(ans[vec[i].id]) continue;
		while(vec[i].r*2<=curC)
		{
			curC/=2; init(curC);
		}
		int x=vec[i].x/curC;
		x=lower_bound(xs.begin(),xs.end(),x)-xs.begin();
		for(int dx=-2;dx<=2;dx++)
		{
			if(x+dx>=0&&x+dx<xs.size()&&abs(xs[x]-xs[x+dx])<=2)
			{
				auto it = lower_bound(V[x+dx].begin(),V[x+dx].end(),mp(vec[i].y/curC - 2, -1));
				for(;it!=V[x+dx].end()&&it->fi<=vec[i].y/curC + 2;it++)
				{
					if(ans[it->se]){continue;}
					if(intersect(a[it->se-1], vec[i]))
					{
						ans[it->se] = vec[i].id; 
					}
				} 
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i];
		if(i+1<=n) cout<<' ';
	}
	cout<<'\n';
}

Compilation message (stderr)

circle_selection.cpp: In function 'void init(int)':
circle_selection.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<xs.size();i++) V[i].clear();
              ~^~~~~~~~~~
circle_selection.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v2.size();i++)
              ~^~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(x+dx>=0&&x+dx<xs.size()&&abs(xs[x]-xs[x+dx])<=2)
                ~~~~^~~~~~~~~~

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