oj.uz

Submission #405407

# Submission time Handle Problem Language Result Execution time Memory
405407 2021-05-16T11:07:48 Z saleh Circle selection (APIO18_circle_selection) C++17
0 / 100
 1 ms 308 KB 
#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(abs(x[a] - x[b]) * abs(x[a] - x[b]) + 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
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 Incorrect 1 ms 204 KB Output isn't correct
3 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 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -