oj.uz

Submission #728309

# Submission time Handle Problem Language Result Execution time Memory
728309 2023-04-22T07:15:41 Z SanguineChameleon Circle selection (APIO18_circle_selection) C++17
50 / 100
 3000 ms 65904 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct circle {
	int x, y, r;
};

bool intersect(circle C1, circle C2) {
	return 1LL * (C1.r + C2.r) * (C1.r + C2.r) >= 1LL * (C1.x - C2.x) * (C1.x - C2.x) + 1LL * (C1.y - C2.y) * (C1.y - C2.y); 
}

const int maxn = 3e5 + 20;
circle C[maxn];
int res[maxn];
set<pair<int, int>> S;
map<pair<int, int>, set<int>> groups;
int n;

int floor(int a, int b) {
	return (a / b) - (a % b && (a ^ b) < 0);
}

void build(int len) {
	groups.clear();
	for (auto p: S) {
		int i = p.second;
		int cx = floor(C[i].x, len);
		int cy = floor(C[i].y, len);
		groups[{cx, cy}].insert(i);
	}
}

void just_do_it() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> C[i].x >> C[i].y >> C[i].r;
		S.insert({-C[i].r, i});
	}
	int len = 2e9 + 20;
	while (!S.empty()) {
		int cur = S.begin()->second;
		if (C[cur].r * 3 < len) {
			len = C[cur].r;
			build(len);
		}
		int cx = floor(C[cur].x, len);
		int cy = floor(C[cur].y, len);
		for (int i = -2; i <= 2; i++) {
			for (int j = -2; j <= 2; j++) {
				auto g_it = groups.find({cx + i, cy + j});
				if (g_it == groups.end()) {
					continue;
				}
				auto it = g_it->second.begin();
				while (it != g_it->second.end()) {
					int can = *it;
					if (intersect(C[cur], C[can])) {
						res[can] = cur;
						it = g_it->second.erase(it);
						S.erase({-C[can].r, can});
					}
					else {
						it++;
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << res[i] << " ";
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Execution timed out 3081 ms 340 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 37728 KB Output is correct
2 Correct 758 ms 37320 KB Output is correct
3 Correct 690 ms 37100 KB Output is correct
4 Correct 624 ms 37356 KB Output is correct
5 Correct 625 ms 37688 KB Output is correct
6 Correct 943 ms 51028 KB Output is correct
7 Correct 732 ms 38788 KB Output is correct
8 Correct 801 ms 41192 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 522 ms 23720 KB Output is correct
3 Correct 2039 ms 65364 KB Output is correct
4 Correct 2029 ms 65344 KB Output is correct
5 Correct 1996 ms 59244 KB Output is correct
6 Correct 733 ms 31248 KB Output is correct
7 Correct 325 ms 17820 KB Output is correct
8 Correct 38 ms 3944 KB Output is correct
9 Correct 2118 ms 64612 KB Output is correct
10 Correct 1757 ms 55584 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1510 ms 65904 KB Output is correct
2 Correct 1111 ms 65568 KB Output is correct
3 Correct 740 ms 44980 KB Output is correct
4 Correct 1123 ms 65576 KB Output is correct
5 Correct 1119 ms 65520 KB Output is correct
6 Correct 620 ms 38100 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Execution timed out 3081 ms 340 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Execution timed out 3081 ms 340 KB Time limit exceeded
9 Halted 0 ms 0 KB -