Submission #734561

#	Time	Username	Problem	Language	Result	Execution time	Memory
734561		hollwo_pelw	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1582 ms	60920 KiB

circle_selection

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 3e5 + 5;

struct circle_t {
	int x, y, r;
} a[N];
int n, len, res[N];

bool intersect(const circle_t &a, const circle_t &b) {
	return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y) <= 1ll * (a.r + b.r) * (a.r + b.r);
}

struct cmp {
	bool operator () (const int &i, const int &j) const {
		return a[i].r > a[j].r || (a[i].r == a[j].r && i < j);
	}
};
set<int, cmp> st;
map<int, vector<pair<int, int>>> grid;

void rebuild() {
	grid.clear();
	for (auto p : st) {
		int x = a[p].x / len, y = a[p].y / len;
		// add (x, y, p)
		grid[x].emplace_back(y, p);
	}
	for (auto &[x, vy] : grid)
		sort(vy.begin(), vy.end());
}

void Hollwo_Pelw(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y >> a[i].r;
		a[i].x += 1e9, a[i].y += 1e9, st.insert(i);
	}

	while (!st.empty()) {
		auto p = *st.begin();
		if ((int) st.size() == n || a[p].r * 2 < len)
			len = a[p].r, rebuild();

		int x = a[p].x / len, y = a[p].y / len;

		for (auto itx = grid.lower_bound(x - 2); itx != grid.end() && itx -> first <= x + 2; itx ++) {
			auto &vy = itx -> second;
			for (auto ity = lower_bound(vy.begin(), vy.end(), pair<int, int>{y - 2, 0}); ity != vy.end() && ity -> first <= y + 2; ity ++) {

				int q = ity -> second;
				if (!res[q] && intersect(a[p], a[q]))
					res[q] = p, st.erase(q);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << res[i] << " \n"[i == n];
	}
}

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