Submission #138612

#	Time	Username	Problem	Language	Result	Execution time	Memory
138612		FedericoS	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3070 ms	23828 KiB

circle_selection

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

int N;
ll X[300005],Y[300005],R[300005];
ll A[300005],P[300005];
vector<pll> V;

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>X[i]>>Y[i]>>R[i];
		V.push_back({-R[i],i});
	}
	sort(V.begin(),V.end());
	for(int i=0;i<N;i++)
		P[i]=V[i].second;

	//for(int i=0;i<N;i++)cout<<P[i]+1<<" ";cout<<endl;

	for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++)
			if(
				(X[P[i]]-X[P[j]])*(X[P[i]]-X[P[j]])+
				(Y[P[i]]-Y[P[j]])*(Y[P[i]]-Y[P[j]])<=
				(R[P[i]]+R[P[j]])*(R[P[i]]+R[P[j]])
				and !A[P[j]] and !A[P[i]]
			)
				A[P[j]]=P[i]+1;

	for(int i=0;i<N;i++)
		cout<<(A[i]?A[i]:(i+1))<<" ";

}

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