/*
Autor kodu: Michał Kaźmierczak
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
vector<array<ll, 3>> info;
vector<array<ll, 3>> points;
vector<ll> ans;
vector<bool> on;
ll grid_length;
ll sq(ll x)
{
return x * x;
}
bool query(ll i, ll j)
{
return (sq(info[i][0] - info[j][0]) + sq(info[i][1] - info[j][1])) <= sq(info[i][2] + info[j][2]);
}
void remake()
{
vector<array<ll, 3>> new_points;
for (auto [x,y,ind] : points)
{
if (!on[ind])
continue;
new_points.push_back({info[ind][0] / grid_length, info[ind][1] / grid_length, ind});
}
swap(points, new_points);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
ans.resize(n);
on.resize(n, 1);
for (ll i = 1, x, y, r; i <= n; i++)
{
cin >> x >> y >> r;
info.push_back({x, y, r});
}
vector<ll> kol(n);
iota(kol.begin(), kol.end(), 0);
sort(kol.begin(), kol.end(), [&](ll a, ll b)
{ return info[a][2] == info[b][2] ? a < b : info[a][2] > info[b][2]; });
grid_length = info[kol[0]][2];
for (ll i = 0; i < n; i++)
{
points.push_back({info[i][0] / grid_length, info[i][1] / grid_length, i});
}
sort(points.begin(), points.end());
for (auto now : kol)
{
if (!on[now])
continue;
if (2 * info[now][2] <= grid_length)
{
grid_length = info[now][2];
remake();
}
ll cur_x = info[now][0] / grid_length;
ll cur_y = info[now][1] / grid_length;
auto lst = points.begin();
auto fin = lower_bound(points.begin(), points.end(), (array<ll, 3>){cur_x + 2, cur_y + 3, -1});
for (ll x = cur_x - 2; x <= cur_x + 2; x++)
{
auto it = lower_bound(lst, fin, (array<ll, 3>){x, cur_y - 2, -1});
for (; it != fin && ((*it)[1] <= cur_y + 2); it++)
{
ll ind = (*it)[2];
if (on[ind] && query(now, ind))
{
on[ind] = false;
ans[ind] = now;
}
}
swap(lst, it);
}
}
for (auto x : ans)
cout << x + 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... |