Submission #73531

#	Time	Username	Problem	Language	Result	Execution time	Memory
73531		KLPP	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3044 ms	44140 KiB

circle_selection

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
#define INF 4000000000
typedef long long int lld;
typedef pair<lld,lld> point;
typedef pair<pair<lld,int>,point> circle;
typedef std::multimap<point,int>::iterator mit;
typedef pair<mit,mit> Range;
 
multimap<point,int> grid;
lld size;
bool B[400000];
circle arr[400000];
int n;
void rescale(){
	size++;
	size/=2;
	grid.clear();
	for(int i=0;i<n;i++){
		if(B[i]){
			point center=arr[i].second;
			center.first/=size;
			center.second/=size;
			grid.insert(pair<point,int>(center,i));
		}
	}
}
lld sq(lld x){
	return x*x;
}
bool eliminates(int i, int j){
	if(sq(arr[i].first.first+arr[j].first.first)>=sq(arr[i].second.first-arr[j].second.first)+sq(arr[i].second.second-arr[j].second.second)){
		return true;
	}return false;
}
void print(){
	for(int i=0;i<n;i++){
		point center=arr[i].second;
		center.first/=size;
		center.second/=size;
		cout<<center.first<<" "<<center.second<<endl;
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){B[i]=true;
		cin>>arr[i].second.first>>arr[i].second.second>>arr[i].first.first;
		arr[i].first.second=-i;
	}
	sort(arr,arr+n);
	reverse(arr,arr+n);
	size=INF;
	int eliminator[n];
	for(int i=0;i<n;i++){
		if(!B[i])continue;

		while(size>2*arr[i].first.first){
			rescale();
		}
		
		int index=-arr[i].first.second;
		lld xgrid=arr[i].second.first/size;
		lld ygrid=arr[i].second.second/size;

		for(lld a=xgrid-2;a<=xgrid+2;a++){
			for(lld b=ygrid-2;b<=ygrid+2;b++){

				Range r=grid.equal_range(point(a,b));
				for(mit it=r.first;it!=r.second;it++){
					int j=it->second;

					if(eliminates(i,j) || i==j){
						
						B[j]=false;
						eliminator[-arr[j].first.second]=-arr[i].first.second;
						mit it2=it;
						grid.erase(it2);
					}
				}
			}
		}
	}
	
	for(int i=0;i<n;i++)cout<<eliminator[i]+1<<" ";
	cout<<endl;
	return 0;	
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:66:7: warning: unused variable 'index' [-Wunused-variable]
   int index=-arr[i].first.second;
       ^~~~~

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