Submission #124214

#	Time	Username	Problem	Language	Result	Execution time	Memory
124214		tutis	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3047 ms	18572 KiB

circle_selection

/*input
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	ll x[n], y[n], r[n];
	for (int i = 0; i < n; i++)
		cin >> x[i] >> y[i] >> r[i];
	int a[n];
	iota(a, a + n, 0);
	sort(a, a + n, [&](int x, int y) {
		if (r[x] != r[y])
			return r[x] > r[y];
		else
			return x < y;
	});
	int ans[n];
	fill_n(ans, n, -1);
	for (int i = 0; i < n; i++)
	{
		if (ans[a[i]] != -1)
			continue;
		for (int j = i; j < n; j++)
		{
			if (ans[a[j]] != -1)
				continue;
			if ((x[a[i]] - x[a[j]]) * (x[a[i]] - x[a[j]]) +
			        (y[a[i]] - y[a[j]]) * (y[a[i]] - y[a[j]]) <=
			        (r[a[i]] + r[a[j]]) * (r[a[i]] + r[a[j]]))
			{
				ans[a[j]] = a[i];
			}
		}
	}
	for (int i = 0; i < n; i++)
		cout << ans[i] + 1 << " ";
	cout << "\n";
}

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