Submission #728328

#	Time	Username	Problem	Language	Result	Execution time	Memory
728328		SanguineChameleon	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1320 ms	60752 KiB

circle_selection

#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<int, vector<pair<int, 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].emplace_back(cy, i);
	}
	for (auto &p: groups) {
		sort(p.second.begin(), p.second.end());
	}
}
 
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 = -1;
	while (!S.empty()) {
		int cur = S.begin()->second;
		if (len == -1 || C[cur].r * 2 < 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++) {
			auto g_it = groups.find({cx + i});
			if (g_it == groups.end()) {
				continue;
			}
			auto it = lower_bound(g_it->second.begin(), g_it->second.end(), make_pair(cy - 2, -1));
			while (it != g_it->second.end()) {
				if (it->first > cy + 2) {
					break;
				}
				int can = it->second;
				if (!res[can] && intersect(C[cur], C[can])) {
					res[can] = cur;
					S.erase({-C[can].r, can});
				}
				it++;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << res[i] << " ";
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13