oj.uz

Submission #453721

# Submission time Handle Problem Language Result Execution time Memory
453721 2021-08-04T16:06:28 Z arminatarod Circle selection (APIO18_circle_selection) C++17
0 / 100
 944 ms 38292 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 300005;

constexpr int MAXINT = 1073741823;

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

int sorted[MAXN], answer[MAXN];

bitset<MAXN> deleted;

set<pair<int, int>> lefts;

set<pair<int, int>> rights;

set<pair<int, int>>::iterator it;

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

vector<int> to_delete;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> circle[i].x >> circle[i].y >> circle[i].radius;
		lefts.emplace(circle[i].x - circle[i].radius, i);
		rights.emplace(circle[i].x + circle[i].radius, i);
		sorted[i] = i;
	}
	sort(sorted, sorted + n, comparison);
	for (int i = 0; i < n; i++)
		if (!deleted[sorted[i]]) {
			to_delete.clear();
			it = lefts.lower_bound(make_pair(circle[sorted[i]].x - circle[sorted[i]].radius, 0));
			while (it != lefts.end() && it->first <= circle[sorted[i]].x + circle[sorted[i]].radius) {
				to_delete.push_back(it->second);
				it++;
			}
			it = rights.lower_bound(make_pair(circle[sorted[i]].x - circle[sorted[i]].radius, 0));
			while (it != rights.end() && it->first <= circle[sorted[i]].x + circle[sorted[i]].radius) {
				to_delete.push_back(it->second);
				it++;
			}
			for (int j : to_delete) {
				lefts.erase(make_pair(circle[j].x - circle[j].radius, j));
				rights.erase(make_pair(circle[j].x - circle[j].radius, j));
				answer[j] = sorted[i];
				deleted[j] = true;
			}
		}
	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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 721 ms 36044 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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