This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define Point pair <int, int>
#define x first
#define y second
const int N = 3e5 + 7;
int n;
Point a[N];
int r[N];
int par[N];
int cur = 1 << 30;
vector<vector<int>> av;
vector<int> px;
int per[N];
bool compx(int i, int j) {
return a[i].x < a[j].x;
}
bool compy(int i, int j) {
return a[i].y < a[j].y;
}
bool used[N];
struct Comp {
bool operator () (const int i, const int j) {
return (r[i] > r[j]) || (r[i] == r[j] && i < j);
}
};
set <int,Comp> ms;
void build() {
av.clear(); px.clear();
int ptr = 0;
while (ptr < n) {
int r = ptr;
while (r + 1 < n && a[per[ptr]].x / cur == a[per[r + 1]].x / cur) ++r;
av.push_back({});
for (int i = ptr; i <= r; ++i) {
av.back().push_back(per[i]);
}
sort(av.back().begin(), av.back().end(), compy);
px.push_back(a[per[ptr]].x / cur);
ptr = r + 1;
}
}
bool intersect(int i, int j) {
typedef long long ll;
return (ll)(a[i].x - a[j].x) * (a[i].x - a[j].x) + (ll)(a[i].y - a[j].y) * (a[i].y - a[j].y) <= (ll)(r[i] + r[j]) * (r[i] + r[j]);
}
void check(int el, int i) {
#ifdef HOME
cout << "check " << el + 1 << ' ' << i + 1 << '\n';
#endif
if (used[i]) return;
if (intersect(el, i)) {
used[i] = 1;
par[i] = el;
ms.erase(i);
}
}
void work(int el, int x, int y) {
auto t = lower_bound(px.begin(), px.end(), x);
if (*t == x) {
int pos = t - px.begin();
#ifdef HOME
cout << "work " << el + 1 << ' ' << pos << '\n';
#endif
int l = -1, r = av[pos].size();
while (l < r - 1) {
int m = (l + r) >> 1;
int i = av[pos][m];
if (a[i].y / cur < y) l = m;
else r = m;
}
for (int i = r; i < (int)av[pos].size(); ++i) {
if (a[av[pos][i]].y / cur != y) {
break;
}
check(el, av[pos][i]);
}
}
}
void print_struct() {
for (int i = 0; i < (int)av.size(); ++i) {
cout << px[i] << " : ";
for (int t : av[i]) cout << t + 1 << ' ';
cout << '\n';
}
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i].x >> a[i].y >> r[i];
}
for (int i = 0; i < n; ++i) {
per[i] = i;
}
sort(per, per + n, compx);
for (int i = 0; i < n; ++i) {
ms.insert(i);
}
build();
while (ms.size()) {
int i = *ms.begin();
while ((cur >> 1) >= r[i]) {
cur >>= 1;
build();
}
#ifdef HOME
cout << "eliminate " << i + 1 << '\n';
cout << "cur " << cur << '\n';
print_struct();
#endif
int ix = a[i].x / cur, iy = a[i].y / cur;
for (int dx = -2; dx <= 2; ++dx) {
for (int dy = -2; dy <= 2; ++dy) {
work(i, ix + dx, iy + dy);
}
}
}
for (int i = 0; i < n; ++i) {
cout << par[i] + 1 << ' ';
}
cout << '\n';
}
# | 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... |