Submission #73568

#	Time	Username	Problem	Language	Result	Execution time	Memory
73568		KLPP	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3092 ms	78976 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].second.first=rand()%1000+1;
		//arr[i].second.second=rand()%1000+1;
		//arr[i].first.first=rand()%1000+1;
		arr[i].first.second=-i;
	}
	sort(arr,arr+n);
	reverse(arr,arr+n);
	size=INF;
	int eliminator[n];
	vector<int> v;
	for(int i=0;i<n;i++){//cout<<i<<endl;
		if(!B[i])continue;

		while(size>2*arr[i].first.first){
			rescale();
		}
		//cout<<i<<endl;
		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++){//cout<<i<<endl;
				Range r=grid.equal_range(point(a,b));
				for(mit it=r.first;it!=r.second && it!=grid.end();it++){//cout<<i<<endl;
					//cout<<it->second<<endl;
					int j=it->second;v.push_back(i);
					if(eliminates(i,j) || i==j){
						B[j]=false;
						eliminator[-arr[j].first.second]=-arr[i].first.second;
						mit it2=it;
						grid.erase(it2);
					}
				}
			}
		}
		
		//cout<<i<<endl;
	}
	
	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:70: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