Submission #1005695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005695		0npata	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1710 ms	103780 KiB

circle_selection

#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int long long

struct Circle {
	int x;
	int y;
	int r;
	int i;
};

bool intersect(Circle& c1, Circle& c2) {
	return (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y) <= (c1.r + c2.r) * (c1.r + c2.r);
}

struct Grid {
	int cell_size = 2e9;
	vec<vec<Circle>> data;

	Grid(vec<Circle> idata, int cell_size) : cell_size(cell_size) {
		sort(idata.begin(), idata.end(), [&](Circle c1, Circle c2) { return c1.x / cell_size < c2.x / cell_size || (c1.x / cell_size == c2.x / cell_size && c1.y < c2.y); });
		data = {};
		vec<Circle> cur{idata[0]};
		for(int i = 1; i<idata.size(); i++) {
			if(idata[i].x/cell_size == cur.back().x/cell_size) {
				cur.push_back(idata[i]);
			}
			else {
				data.push_back(cur);
				cur = {idata[i]};
			}
		}
		data.push_back(cur);
	}

	vec<Circle> query(Circle c) {
		int cell_span = c.r*2 / cell_size + 1;
		int cx = c.x / cell_size;
		int cy = c.y / cell_size;
		auto it = lower_bound(data.begin(), data.end(), cx-cell_span, [&](vec<Circle>& col, int x) { return col[0].x / cell_size < x; });

		vec<Circle> res{};
		for(int i = it-data.begin(); i < data.size() && data[i][0].x / cell_size <= cx + cell_span; i++) {
			auto it = lower_bound(data[i].begin(), data[i].end(), cy-cell_span, [&](Circle& oc, int val) {return oc.y / cell_size < val;});
			int j = it-data[i].begin();
			for(; j < data[i].size() && data[i][j].y / cell_size <= cy + cell_span; j++) {
				res.push_back(data[i][j]);
			}
		}

		return res;
	}
};

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);



	int n;
	cin >> n;
	vec<Circle> cs(n);
	for(int i = 0; i<n; i++) {
		cs[i].i = i;
		cin >> cs[i].x >> cs[i].y >> cs[i].r;
	}


	vec<int> ans(n, -1);

	sort(cs.begin(), cs.end(), [](Circle c1, Circle c2) { return c1.r > c2.r || (c1.r == c2.r && c1.i < c2.i); });

	Grid grid(cs, 1e9);

	for(int i = 0; i<n; i++) {
		if(ans[cs[i].i] != -1) continue;

		while(grid.cell_size > 2*cs[i].r) {
			grid = Grid(cs, grid.cell_size/2);
		}

		vec<Circle> near = grid.query(cs[i]);
		for(Circle& c : near) {
			if(ans[c.i] != -1) continue;
			if(intersect(cs[i], c)) {
				ans[c.i] = cs[i].i;
			}
		}
	}

	for(int i = 0; i<n; i++) {
		assert(ans[i] != -1);
		cout << ans[i]+1 << ' ';
	}
	cout << '\n';
}

Compilation message (stderr)

circle_selection.cpp: In constructor 'Grid::Grid(std::vector<Circle>, long long int)':
circle_selection.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Circle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i = 1; i<idata.size(); i++) {
      |                  ~^~~~~~~~~~~~~
circle_selection.cpp: In member function 'std::vector<Circle> Grid::query(Circle)':
circle_selection.cpp:45:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<Circle> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i = it-data.begin(); i < data.size() && data[i][0].x / cell_size <= cx + cell_span; i++) {
      |                                ~~^~~~~~~~~~~~~
circle_selection.cpp:48:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Circle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(; j < data[i].size() && data[i][j].y / cell_size <= cy + cell_span; j++) {
      |          ~~^~~~~~~~~~~~~~~~

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