이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
struct circle {
int x, y, r, index;
};
vector <vector <circle> > build_matrix(vector <circle> circles, int sz) {
sort(circles.begin(), circles.end(), [](const circle &a, const circle &b) {
return a.x < b.x;
});
int n = (int) circles.size();
vector <circle> cur;
vector <vector <circle> > res;
for (int i = 0; i < n; i++) {
if (cur.empty() || cur.back().x / sz == circles[i].x / sz) {
cur.push_back(circles[i]);
} else {
res.push_back(cur);
cur = {circles[i]};
}
}
if (!cur.empty()) {
res.push_back(cur);
}
for (auto &to : res) {
sort(to.begin(), to.end(), [](const circle &a, const circle &b) {
return a.y < b.y;
});
}
return res;
}
bool query(const circle &a, const circle &b) {
long long distance = (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y);
return distance <= (a.r + b.r) * 1ll * (a.r + b.r);
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector <circle> c;
set <pair <int, int>, greater <pair <int, int> > > rads;
for (int i = 0; i < n; i++) {
int x, y, r;
cin >> x >> y >> r;
c.push_back({x, y, r, i});
rads.insert({r, -i});
}
int sz = rads.begin()->first;
auto result = build_matrix(c, sz);
vector <int> rem(n, -1);
for (int i = 0; i < n; i++) {
auto it = rads.begin();
int index = -it->second;
int cur_rad = it->first;
rads.erase(it);
if (rem[index] != -1) {
continue;
}
rem[index] = index;
if (cur_rad <= sz / 2) {
sz /= 2;
result = build_matrix(c, sz);
}
int xl = n, xr = -1;
{
int starting_point = (c[index].x / sz) * sz;
int prev_point = starting_point - 2 * sz;
int l = 0, r = (int) result.size() - 1;
int res = n;
while (l <= r) {
int mid = (l + r) / 2;
if (result[mid][0].x >= prev_point) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
xl = res;
}
{
int starting_point = (c[index].x / sz) * sz;
int next_point = starting_point + 3 * sz;
int l = 0, r = (int) result.size() - 1;
int res = n;
while (l <= r) {
int mid = (l + r) / 2;
if (result[mid][0].x >= next_point) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
xr = res;
xr--;
}
xl = max(0ll, xl);
xr = min((int) result.size() - 1, xr);
for (int j = xl; j <= xr; j++) {
int yl = n, yr = -1;
{
int starting_point = (c[index].y / sz) * sz;
int prev_point = starting_point - 2 * sz;
int l = 0, r = (int) result[j].size() - 1;
int res = n;
while (l <= r) {
int mid = (l + r) / 2;
if (result[j][mid].y >= prev_point) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
yl = res;
}
{
int starting_point = (c[index].y / sz) * sz;
int next_point = starting_point + 3 * sz;
int l = 0, r = (int) result[j].size() - 1;
int res = n;
while (l <= r) {
int mid = (l + r) / 2;
if (result[j][mid].y >= next_point) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
yr = res;
yr--;
}
yl = max(0ll, yl);
yr = min((int) result[j].size() - 1, yr);
for (int k = yl; k <= yr; k++) {
if (rem[result[j][k].index] == -1 && query(c[index], result[j][k])) {
rem[result[j][k].index] = index;
}
}
}
}
for (int i = 0; i < n; i++) {
cout << rem[i] + 1 << ' ';
}
cout << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |