#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++) {
| ~~^~~~~~~~~~~~~~~~
# |
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 |
- |
# |
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 |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
522 ms |
137424 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
- |
# |
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 |
- |