Submission #1358160

#TimeUsernameProblemLanguageResultExecution timeMemory
1358160khangai11Circle selection (APIO18_circle_selection)C++20
7 / 100
3095 ms18932 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool aa(pair<ll,ll> a,pair<ll,ll> b){
	if(a.first!=b.first)return (a.first>b.first);
	return (a.second<b.second);
}
void solve(){
	ll n;
	cin>>n;
	vector<ll> x(n),y(n),r(n);
	vector<pair<ll,ll>> A;
	for(ll a=0;a<n;a++){
		cin>>x[a]>>y[a]>>r[a];
		A.push_back({r[a],a});
	}
	sort(A.begin(),A.end(),aa);
	vector<ll> rm(n,0),ans(n);
	for(ll a=0;a<n;a++){
		if(rm[A[a].second]==1){
			continue;
		}
		rm[A[a].second]=1;
		ans[A[a].second]=A[a].second+1;
		for(ll b=0;b<n;b++){
			if(rm[b]==0){
				ll x1=x[A[a].second],y1=y[A[a].second],r1=r[A[a].second];
				ll x2=x[b],y2=y[b],r2=r[b];
				if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(r1+r2)*(r1+r2)){
					ans[b]=A[a].second+1;
					rm[b]=1;
				}
			}
		}
	}
	for(ll a=0;a<n;a++){
		cout<<ans[a]<<" ";
	}
}
signed main(){
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	ll t=1;
//	cin>>t;
	for(ll a=0;a<t;a++){
		solve();
	}
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...