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;
int N, x[300009], y[300009], r[300009], id[300009], oldOrd[300009], ord[300009], ans[300009];
pair < int, int > h[300009];
bool cmp (int i, int j)
{
if (r[i] == r[j]) return (i < j);
return (r[i] > r[j]);
}
unsigned int K = 1 << 31;
void doubleGrid ()
{
memcpy (oldOrd, ord, sizeof (ord));
int M = 0;
for (int i=1; i<=N; i++)
{
int j = i;
while (j < N && h[j + 1].first == h[j].first) j++;
for (int k=0; k<2; k++)
for (int l=i; l<=j; l++)
{
int r = l;
while (r < j && h[r + 1].second == h[l].second) r ++;
///playing with [l, r]
for (int p=0; p<2; p++)
for (int pos=l; pos<=r; pos++)
if (((x[oldOrd[pos]] % K) >= K / 2) == k &&
((y[oldOrd[pos]] % K) >= K / 2) == p)
ord[++M] = oldOrd[pos];
///
l = r;
}
i = j;
}
K /= 2;
for (int i=1; i<=N; i++)
h[i] = {x[ord[i]] / K, y[ord[i]] / K};
}
bool query (int i, int j)
{
return (1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]) <= 1LL * (r[i] + r[j]) * (r[i] + r[j]));
}
void eliminate (int pos)
{
int a = x[pos] / K, b = y[pos] / K;
for (int i=max (a - 2, 0); i<=a + 2; i++)
{
pair < int, int > mi = {i, b - 2}, ma = {i, b + 2};
int j = lower_bound (h + 1, h + N + 1, mi) - h, k;
if (h[j].first != i || h[j].second > b + 2) continue;
k = upper_bound (h + 1, h + N + 1, ma) - h - 1;
for (int p=j; p<=k; p++)
if (ans[ord[p]] == 0 && query (pos, ord[p]))
ans[ord[p]] = pos;
}
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d", &N);
for (int i=1; i<=N; i++)
scanf ("%d %d %d", &x[i], &y[i], &r[i]),
x[i] += 1e9, y[i] += 1e9,
ord[i] = i, h[i] = {0, 0}, id[i] = i;
sort (id + 1, id + N + 1, cmp);
for (int i=1; i<=N; i++)
{
while (K / 2 >= r[id[i]])
doubleGrid ();
if (ans[id[i]] == 0)
eliminate (id[i]);
}
for (int i=1; i<=N; i++)
printf ("%d%c", ans[i], " \n"[i == N]);
return 0;
}
Compilation message (stderr)
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (K / 2 >= r[id[i]])
~~~~~~^~~~~~~~~~~
circle_selection.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
circle_selection.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d %d", &x[i], &y[i], &r[i]),
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
x[i] += 1e9, y[i] += 1e9,
~~~~~~~~~~~~~~~~~~~~~~~~~~
ord[i] = i, h[i] = {0, 0}, id[i] = i;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
# | 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... |