Submission #835640

#	Time	Username	Problem	Language	Result	Execution time	Memory
835640		jamielim	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1868 ms	52772 KiB

circle_selection

#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];
ll scale=(1LL<<32);
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>2*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++){
				if(m.find(mp(i,j))==m.end())continue;
				vector<int> &v1=m[mp(i,j)];
				vector<int> v2;
				for(int k:v1){
					if(ans[k]==-1&&intersect(k,index)){
						ans[k]=index;
					}else if(ans[k]==-1){
						v2.pb(k);
					}
				}
				swap(m[mp(i,j)],v2);
			}
		}
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]+1);
}

Compilation message (stderr)

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]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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