oj.uz

Submission #1005691

# Submission time Handle Problem Language Result Execution time Memory
1005691 2024-06-22T18:57:57 Z 0npata Circle selection (APIO18_circle_selection) C++17
12 / 100
 522 ms 137424 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 = 20;
		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& 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);


	cerr << -1/4 << '\n';

	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:44: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]
   44 |   for(int i = it-data.begin(); i < data.size() && data[i][0].x / cell_size <= cx + cell_span; i++) {
      |                                ~~^~~~~~~~~~~~~
circle_selection.cpp:46:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Circle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for(int j = it - data[i].begin(); j < data[i].size() && data[i][j].y / cell_size <= cy + cell_span; j++) {
      |                                      ~~^~~~~~~~~~~~~~~~

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 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 69864 KB Output is correct
2 Correct 160 ms 67160 KB Output is correct
3 Correct 145 ms 75764 KB Output is correct
4 Correct 152 ms 70608 KB Output is correct
5 Correct 353 ms 81060 KB Output is correct
6 Correct 414 ms 98688 KB Output is correct
7 Correct 397 ms 87172 KB Output is correct
8 Correct 362 ms 91528 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 522 ms 137424 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 6
12 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 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -