Submission #453693

#	Time	Username	Problem	Language	Result	Execution time	Memory
453693		arminatarod	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3119 ms	714892 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 200005;

constexpr int MAXINT = 1073741823;

vector<int> neighbors[MAXN];

struct circles {
	long long int x, y, radius;
} circle[MAXN];

int sorted[MAXN], answer[MAXN];

bitset<MAXN> deleted;

bool comparison(int x, int y) {
	return (circle[x].radius == circle[y].radius? x < y : circle[x].radius > circle[y].radius);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long int n, distance_2, radius_2;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> circle[i].x >> circle[i].y >> circle[i].radius;
		sorted[i] = i;
	}
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			distance_2 = (circle[i].x - circle[j].x) * (circle[i].x - circle[j].x) + (circle[i].y - circle[j].y) * (circle[i].y - circle[j].y);
			radius_2 = (circle[i].radius + circle[j].radius) * (circle[i].radius + circle[j].radius);
			if (radius_2 >= distance_2) {
				neighbors[i].push_back(j);
				neighbors[j].push_back(i);
			}
		}
	sort(sorted, sorted + n, comparison);
	for (int i = 0; i < n; i++)
		if (!deleted[sorted[i]]) {
			answer[sorted[i]] = sorted[i];
			deleted[sorted[i]] = true;
			for (int j : neighbors[sorted[i]]) {
				if (deleted[j])
					continue;
				answer[j] = sorted[i];
				deleted[j] = true;
			}
		}
	for (int i = 0; i < n; i++)
		cout << answer[i] + 1 << ' ';
	return 0;
}

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