Submission #263285

#	Time	Username	Problem	Language	Result	Execution time	Memory
263285		dsjong	Circle selection (APIO18_circle_selection)	C++14	7 / 100	67 ms	1920 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define F first
#define S second
int ans[5005];
int x[5005], y[5005], r[5005];
bool isct(int i, int j){
	int md=(r[i]+r[j])*(r[i]+r[j]);
	int d=(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
	return d<=md;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<pii>v;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>r[i];
		v.push_back({r[i], -i});
	}
	sort(v.begin(), v.end());
	while(!v.empty()){
		int cur=-v.back().S;
		v.pop_back();
		if(ans[cur]) continue;
		for(int i=1;i<=n;i++){
			if(isct(i, cur) && ans[i]==0) ans[i]=cur;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}

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