oj.uz

Submission #405144

# Submission time Handle Problem Language Result Execution time Memory
405144 2021-05-15T18:47:54 Z BERNARB01 Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 24232 KB 
#include <bits/stdc++.h>

using namespace std;

long double dist(long long x, long long y, long long xx, long long yy) {
	return sqrtl((x - xx) * (x - xx) + (y - yy) * (y - yy));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> x(n), y(n), r(n);
	set<pair<int, int>> ms;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> r[i];
		ms.insert({-r[i], i});
	}
	vector<int> a(n, -1);
	while (!ms.empty()) {
		int jj = ms.begin()->second;
		a[jj] = jj;
		ms.erase(ms.begin());
		for (int i = 0; i < n; i++) {
			if (a[i] == -1) {
				if (dist(x[i], y[i], x[jj], y[jj]) <= (long double) r[i] + r[jj]) {
					a[i] = jj;
					ms.erase({-r[i], i});
				}
			}
		}
	}
	for (const auto& xx : a) {
		cout << xx + 1 << " ";
	}
	cout << '\n';
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 320 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 5 ms 716 KB Output is correct
20 Correct 5 ms 772 KB Output is correct
21 Correct 5 ms 732 KB Output is correct
22 Correct 123 ms 736 KB Output is correct
23 Correct 119 ms 744 KB Output is correct
24 Correct 119 ms 760 KB Output is correct
25 Correct 122 ms 748 KB Output is correct
26 Correct 122 ms 836 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 21212 KB Output is correct
2 Correct 498 ms 24172 KB Output is correct
3 Correct 492 ms 23968 KB Output is correct
4 Correct 489 ms 24232 KB Output is correct
5 Execution timed out 3046 ms 21996 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 3017 ms 8644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 19084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 320 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 5 ms 716 KB Output is correct
20 Correct 5 ms 772 KB Output is correct
21 Correct 5 ms 732 KB Output is correct
22 Correct 123 ms 736 KB Output is correct
23 Correct 119 ms 744 KB Output is correct
24 Correct 119 ms 760 KB Output is correct
25 Correct 122 ms 748 KB Output is correct
26 Correct 122 ms 836 KB Output is correct
27 Correct 11 ms 1220 KB Output is correct
28 Correct 10 ms 1228 KB Output is correct
29 Correct 10 ms 1232 KB Output is correct
30 Correct 495 ms 1220 KB Output is correct
31 Correct 505 ms 1220 KB Output is correct
32 Correct 491 ms 1220 KB Output is correct
33 Correct 117 ms 9412 KB Output is correct
34 Correct 114 ms 9384 KB Output is correct
35 Correct 119 ms 9408 KB Output is correct
36 Execution timed out 3036 ms 8384 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 320 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 5 ms 716 KB Output is correct
20 Correct 5 ms 772 KB Output is correct
21 Correct 5 ms 732 KB Output is correct
22 Correct 123 ms 736 KB Output is correct
23 Correct 119 ms 744 KB Output is correct
24 Correct 119 ms 760 KB Output is correct
25 Correct 122 ms 748 KB Output is correct
26 Correct 122 ms 836 KB Output is correct
27 Correct 445 ms 21212 KB Output is correct
28 Correct 498 ms 24172 KB Output is correct
29 Correct 492 ms 23968 KB Output is correct
30 Correct 489 ms 24232 KB Output is correct
31 Execution timed out 3046 ms 21996 KB Time limit exceeded
32 Halted 0 ms 0 KB -