Submission #54465

#TimeUsernameProblemLanguageResultExecution timeMemory
54465SpaimaCarpatilorCircle selection (APIO18_circle_selection)C++17
100 / 100
1938 ms447580 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...