Submission #1262923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262923		4QT0R	Circle selection (APIO18_circle_selection)	C++20	7 / 100	3095 ms	32916 KiB

circle_selection

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

ll n;
vector<array<ll, 3>> info;
vector<ll> ans;
unordered_set<ll> on;

ll sq(ll x)
{
	return x * x;
}

bool query(ll i, ll j)
{
	return (sq(info[i][0] - info[j][0]) + sq(info[i][1] - info[j][1])) <= sq(info[i][2] + info[j][2]);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	ans.resize(n);
	for (ll i = 1, x, y, r; i <= n; i++)
	{
		cin >> x >> y >> r;
		info.push_back({x, y, r});
		on.insert(i-1);
	}
	vector<ll> kol(n);
	iota(kol.begin(), kol.end(), 0);
	sort(kol.begin(), kol.end(), [&](ll a, ll b)
		 { return info[a][2] == info[b][2] ? a < b : info[a][2] > info[b][2]; });
	for (auto now : kol)
	{
		if (!on.count(now))
			continue;
		vector<ll> to_remove;
		for (auto u : on)
		{
			if (query(now, u))
			{
				ans[u] = now;
				to_remove.push_back(u);
			}
		}
		while(to_remove.size()){
			on.erase(to_remove.back());
			to_remove.pop_back();
		}
	}
	for (auto x : ans)
		cout << x + 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