oj.uz

Submission #453692

# Submission time Handle Problem Language Result Execution time Memory
453692 2021-08-04T15:23:19 Z arminatarod Circle selection (APIO18_circle_selection) C++17
0 / 100
 127 ms 33716 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 200005;

constexpr int MAXINT = 1073741823;

set<int> neighbors[MAXN];

struct circles {
	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);
	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].insert(j);
				neighbors[j].insert(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]]) {
				answer[j] = sorted[i];
				deleted[j] = true;
				for (int k : neighbors[j])
					if (k != sorted[i])
						neighbors[k].erase(j);
			}
		}
	for (int i = 0; i < n; i++)
		cout << answer[i] + 1 << ' ';
	return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 32452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 33716 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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