Submission #1160144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160144		xnqs	Circle selection (APIO18_circle_selection)	C++20	64 / 100	3115 ms	585896 KiB

circle_selection

#pragma GCC optimize("Ofast")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <list>

struct Circle {
	int x, y, r, idx;
	Circle():
		x(0), y(0), r(0), idx(0) {}
	Circle(int x, int y, int r, int idx):
		x(x), y(y), r(r), idx(idx) {}

	bool operator == (const Circle& other) const {
		if (this->x!=other.x) return 0;
		if (this->y!=other.y) return 0;
		if (this->r!=other.r) return 0;
		if (this->idx!=other.idx) return 0;
		return 1;
	}
};

struct PairHasher {
	std::size_t operator() (const std::pair<int,int>& p) const {
		return p.first * 1000000006ULL + p.second;
	}
};

int n;
std::unordered_set<int> active;
std::vector<Circle> circles;
std::vector<int> eliminator;
int idx_r[500005];

int grid_size;
std::unordered_map<std::pair<int,int>, std::list<int>, PairHasher> grid;

inline int64_t euclid_dist(int x1, int y1, int x2, int y2) {
	return 1LL*(x1-x2)*(x1-x2) + 1LL*(y1-y2)*(y1-y2);
}

/*
	d(a,b) - a.r <= b.r
	sqrt((a.x-b.x)^2 + (a.y-b.y)^2) - a.r <= b.r
	sqrt((a.x-b.x)^2 + (a.y-b.y)^2) <= b.r + a.r
	(a.x-b.x)^2 + (a.y-b.y)^2 <= (b.r + a.r)^2
*/
inline bool intersect(const Circle& a, const Circle& b) {
	return euclid_dist(a.x,a.y,b.x,b.y) <= 1LL*(a.r+b.r)*(a.r+b.r);
}

void init_grid(int size) {
	grid.clear();
	grid_size = size;
	for (auto i : active) {
		grid[std::pair<int,int>(circles[i].x/size,circles[i].y/size)].emplace_back(i);
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> n;
	for (int i = 0, x, y, r; i < n; i++) {
		active.emplace(i);
		std::cin >> x >> y >> r;
		circles.emplace_back(x,y,r,i);
	}

	std::sort(circles.begin(),circles.end(),[](const Circle& a, const Circle& b) {
		if (a.r!=b.r) return a.r > b.r;
		return a.idx < b.idx;
	});

	for (int i = 0; i < n; i++) {
		idx_r[circles[i].idx] = i;
	}

	eliminator.assign(n, 0);
	init_grid(circles[0].r);
	for (const auto& c : circles) {
		const auto& [x, y, r, idx] = c;
		if (r < grid_size/2) {
			init_grid(r);
		}
		if (eliminator[idx]) {
			continue;
		}

		eliminator[idx] = idx+1;
		active.erase(idx_r[idx]);

		//std::cout << idx << " " << grid_size << "\n";

		int grid_x = x / grid_size;
		int grid_y = y / grid_size;

		for (int gx = grid_x-2; gx <= grid_x+2; gx++) {
			for (int gy = grid_y-2; gy <= grid_y+2; gy++) {
				auto& tmp = grid[std::pair<int,int>(gx,gy)];
				for (auto it = tmp.begin(); it != tmp.end();) {
					int i = *it;

					if (intersect(c, circles[i])) {
						eliminator[circles[i].idx] = idx+1;
						active.erase(idx_r[circles[i].idx]);
						it = tmp.erase(it);
					}
					else {
						++it;
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		std::cout << eliminator[i] << " ";
	}
	std::cout << "\n";
}

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