oj.uz

Submission #1005687

# Submission time Handle Problem Language Result Execution time Memory
1005687 2024-06-22T18:50:36 Z 0npata Circle selection (APIO18_circle_selection) C++17
12 / 100
 430 ms 142076 KB 
#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) {
		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 = 2*c.r / cell_size + 2;
		int cx = c.x / cell_size;
		int cy = c.y / cell_size;
		int l = 0;
		int r = data.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& c, int val) {return c.y / cell_size < val;});
			for(int j = it - data[i].begin(); 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); });

	vec<Circle> idata = cs;
	sort(idata.begin(), idata.end(), [](Circle c1, Circle c2) { return c1.x < c2.x || (c1.x == c2.x && c1.y < c2.y); });
	Grid grid(idata, 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(idata, 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

circle_selection.cpp: In constructor 'Grid::Grid(std::vector<Circle>, long long int)':
circle_selection.cpp:25:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Circle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i = 1; i<idata.size(); i++) {
      |                  ~^~~~~~~~~~~~~
circle_selection.cpp: In member function 'std::vector<Circle> Grid::query(Circle)':
circle_selection.cpp:46: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]
   46 |   for(int i = it-data.begin(); i < data.size() && data[i][0].x / cell_size <= cx + cell_span; i++) {
      |                                ~~^~~~~~~~~~~~~
circle_selection.cpp:48:40: 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(int j = it - data[i].begin(); j < data[i].size() && data[i][j].y / cell_size <= cy + cell_span; j++) {
      |                                      ~~^~~~~~~~~~~~~~~~
circle_selection.cpp:41:7: warning: unused variable 'l' [-Wunused-variable]
   41 |   int l = 0;
      |       ^
circle_selection.cpp:42:7: warning: unused variable 'r' [-Wunused-variable]
   42 |   int r = data.size();
      |       ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 76908 KB Output is correct
2 Correct 163 ms 72948 KB Output is correct
3 Correct 159 ms 83760 KB Output is correct
4 Correct 151 ms 64740 KB Output is correct
5 Correct 357 ms 82996 KB Output is correct
6 Correct 430 ms 100928 KB Output is correct
7 Correct 347 ms 90536 KB Output is correct
8 Correct 327 ms 96540 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 333 ms 142076 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -