Submission #405408

#	Time	Username	Problem	Language	Result	Execution time	Memory
405408		saleh	Circle selection (APIO18_circle_selection)	C++17	7 / 100	264 ms	756 KiB

circle_selection

#include <bits/stdc++.h>


using namespace std;


const int MAXN = 5000 + 3;



/*
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
*/











int n, x[MAXN], y[MAXN], r[MAXN], par[MAXN];

struct cmp { bool operator ()(int a, int b) const { return r[a] > r[b]? true: (r[a] == r[b]? a < b: false); } };
set<int, cmp> s;

auto dis(int a, int b) { return sqrt(1ll * abs(x[a] - x[b]) * abs(x[a] - x[b]) + 1ll * abs(y[a] - y[b]) * abs(y[a] - y[b])); }
bool sect(int a, int b) { return dis(a, b) <= r[a] + r[b]; }


int main() {
	cin >> n;
	if (n >= MAXN) return 0;
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> r[i];
	for (int i = 0; i < n; i++) s.insert(i);
	while (!s.empty()) {
		int x = *s.begin();
		for (auto i = s.begin(); i != s.end(); ) if (sect(*i, x)) {
			par[*i] = x;
			i = s.erase(i);
		} else i++;
	}
	for (int i = 0; i < n; i++) cout << par[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