Submission #1172702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172702		stdfloat	Circle selection (APIO18_circle_selection)	C++20	0 / 100	138 ms	9936 KiB

circle_selection

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

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

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

	int n;
	cin >> n;

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

	sort(p1 + 1, p1 + n + 1, [&](pii x, pii y) {
		return (x.ff > y.ff || (x.ff == y.ff && x.ss < y.ss));
	});
	sort(p2 + 1, p2 + n + 1);

	vector<int> ans(n + 1);
	for (int i = 1; i <= n; i++) {
		int ind = p1[i].ss;
		if (ans[ind]) continue;

		int L = lower_bound(p2 + 1, p2 + n + 1, pii{x[ind], ind}) - p2, R = L;
		while (0 < L && !ans[L] && x[ind] - p2[L].ff <= r[ind]) {
			ans[p2[L].ss] = ind;
			L--;
		}
		while (R <= n && !ans[R] && p2[R].ff - x[ind] <= r[ind]) {
			ans[p2[R].ss] = ind;
			R++;
		}
	}

	for (int i = 1; i <= n; i++)
		cout << ans[i] << ' ';
}

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