Submission #1172695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172695		stdfloat	Circle selection (APIO18_circle_selection)	C++20	7 / 100	3094 ms	8312 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;

	vector<int> x(n + 1), y(n + 1), r(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i] >> r[i];

	vector<int> ord(n + 1);
	iota(ord.begin() + 1, ord.end(), 1);
	sort(ord.begin() + 1, ord.end(), [&](int x, int y) {
		return (r[x] > r[y] || (r[x] == r[y] && x < y));
	});

	vector<int> ans(n + 1);
	for (auto i : ord) {
		if (ans[i]) continue;

		for (int j = 1; j <= n; j++)
			if (!ans[j] && (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]) <= (ll)(r[i] + r[j]) * (r[i] + r[j])) ans[j] = i;
	}

	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