Submission #356694

#	Time	Username	Problem	Language	Result	Execution time	Memory
356694		CaroLinda	Circle selection (APIO18_circle_selection)	C++14	87 / 100	3076 ms	59860 KiB

circle_selection

/*
Proof of complexity: https://en.wikipedia.org/wiki/Circle_packing_in_a_square
*/
 
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()
 
const int MAXN = 3e5+10 ;
 
using namespace std ;
 
struct Circle
{
	ll x , y , r ;
	int id ;
 
	Circle(ll x = 0 , ll y = 0 , ll r = 0 , int id =0 ) : x(x), y(y) , r(r) , id(id){}
 
} circle[MAXN] ;
 
int N ;
int ans[MAXN] ;
ll G ;
vector<ll> p ;
set< pair<ll, int> > s[MAXN] ;
 
bool test(int x, int y )
{
	ll dx =p[ circle[x].x ] - p[ circle[y].x] ;
	ll dy = circle[x].y - circle[y].y ;
	ll r = circle[x].r + circle[y].r ;
	return dx*dx + dy*dy <= r*r ;
}
 
int main()
{
 
	scanf("%d", &N ) ;
	for(int i = 0 ; i < N ; i++ )
	{
		scanf("%lld %lld %lld", &circle[i].x, &circle[i].y, &circle[i].r ) ;
		circle[i].id = i ;
		p.push_back(circle[i].x) ;
	} 
 
	vector<int> vec(N) ; iota(all(vec) , 0 ) ;
	sort(all(vec), [&](int i, int j )
	{
		if( circle[i].r != circle[j].r ) return circle[i].r > circle[j].r ;
		return i < j ;
	} ) ; 
 
	sort(all(p) ) ;
	p.erase(unique(all(p)),p.end() ) ;	
 
	for(int i = 0 ; i < N ; i++ )
	{
		circle[i].x = lower_bound(all(p), circle[i].x ) - p.begin() ;
		s[circle[i].x].insert( make_pair(circle[i].y, i) ) ;		
		ans[i] = -1 ;
	}

	G = circle[vec[0]].r ;
 
	for(int e : vec )
	{
		if(ans[e] != -1 ) continue ;	

		G =  circle[e].r ;

		ll lo = circle[e].y - G - G ;
		ll hi = circle[e].y + G + G ;
 
		vector<int> toErase ;
 
		int l = lower_bound(all(p), p[circle[e].x] - G - G ) - p.begin() ;
		int r = upper_bound(all(p), p[circle[e].x] + G + G ) - p.begin() - 1 ;


		for(int i = l ; i <= r ; i++ )
		{
			auto it = s[i].lower_bound( make_pair(lo, -1 ) ) ;
 
			while( it != s[i].end() && it->first <= hi )
			{
				if( test(it->second, e) ) 
				{
					toErase.push_back(it->second) ;
					ans[it->second] = e ;
				}
				it++ ;
			}
		}
 
		for(auto ee : toErase )
			s[ circle[ee].x ].erase( s[circle[ee].x].find(make_pair(circle[ee].y, ee ) ) ) ;
 
	}
 
	for(int i = 0 ; i < N ; i++ ) printf("%d ", ans[i]+1 ) ;
	printf("\n") ; 
 
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
circle_selection.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   scanf("%lld %lld %lld", &circle[i].x, &circle[i].y, &circle[i].r ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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