oj.uz

Submission #1005688

# Submission time Handle Problem Language Result Execution time Memory
1005688 2024-06-22T18:52:34 Z 0npata Circle selection (APIO18_circle_selection) C++17
12 / 100
 367 ms 97380 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++) {
		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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 71340 KB Output is correct
2 Correct 173 ms 66740 KB Output is correct
3 Correct 155 ms 77968 KB Output is correct
4 Correct 166 ms 59968 KB Output is correct
5 Correct 322 ms 79620 KB Output is correct
6 Correct 367 ms 97380 KB Output is correct
7 Correct 309 ms 86020 KB Output is correct
8 Correct 347 ms 96104 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 67632 KB Output isn't correct
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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -