Submission #727711

#	Time	Username	Problem	Language	Result	Execution time	Memory
727711		SanguineChameleon	Circle selection (APIO18_circle_selection)	C++17	7 / 100	126 ms	1056 KiB

circle_selection

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct circle {
	long long x, y, r;
};

const int maxn = 5e3 + 20;
circle C[maxn];
int res[maxn];

bool intersect(circle C1, circle C2) {
	return (C1.r + C2.r) * (C1.r + C2.r) >= (C1.x - C2.x) * (C1.x - C2.x) + (C1.y - C2.y) * (C1.y - C2.y);
};

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> C[i].x >> C[i].y >> C[i].r;
	}
	while (true) {
		int best = -1;
		for (int i = 1; i <= n; i++) {
			if (!res[i]) {
				if (best == -1 || C[best].r < C[i].r) {
					best = i;
				}
			}
		}
		if (best == -1) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			if (!res[i] && intersect(C[i], C[best])) {
				res[i] = best;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << res[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