Submission #111810

#	Time	Username	Problem	Language	Result	Execution time	Memory
111810		b2563125	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3098 ms	17452 KiB

circle_selection

#include<iostream>
#include<vector>
#include<algorithm>
#define vel vector<long long>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pin pair<int,int>
#define mkp make_pair
#define sor(v) sort(v.begin(),v.end())
#define int long long
int sq(int n) { return n * n; }
int dist(vel &x, vel &y, int i, int j) {
	return sq(x[i] - x[j]) + sq(y[i] - y[j]);
}
signed main() {
	int n; cin >> n;
	vel x(n), y(n), r(n);
	vector<pin> al(n);
	rep(i, n) { cin >> x[i] >> y[i] >> r[i]; al[i] = mkp(-r[i], i); }
	vector<bool> is_kled(n, false);
	vel ans(n);
	sor(al);
	rep(i, n) {
		int ri = al[i].second;
		if (!is_kled[ri]) {
			rep(j, n) {
				if (!is_kled[j] and (dist(x, y, ri, j) <= sq(r[ri] + r[j]) )) {
					ans[j] = ri;
					is_kled[j] = true;
				}
			}
		}
	}
	rep(i, n) { cout << ans[i]+1<<endl; }
	return 0;
}

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