oj.uz

Submission #54465

# Submission time Handle Problem Language Result Execution time Memory
54465 2018-07-03T14:43:00 Z SpaimaCarpatilor Circle selection (APIO18_circle_selection) C++17
100 / 100
 1938 ms 447580 KB 
#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

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;
     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1740 KB Output is correct
5 Correct 4 ms 1756 KB Output is correct
6 Correct 6 ms 1808 KB Output is correct
7 Correct 5 ms 1948 KB Output is correct
8 Correct 4 ms 1948 KB Output is correct
9 Correct 5 ms 1948 KB Output is correct
10 Correct 5 ms 1948 KB Output is correct
11 Correct 5 ms 1948 KB Output is correct
12 Correct 6 ms 1948 KB Output is correct
13 Correct 7 ms 1948 KB Output is correct
14 Correct 5 ms 1948 KB Output is correct
15 Correct 6 ms 1948 KB Output is correct
16 Correct 7 ms 1948 KB Output is correct
17 Correct 6 ms 1948 KB Output is correct
18 Correct 6 ms 1948 KB Output is correct
19 Correct 15 ms 2312 KB Output is correct
20 Correct 13 ms 2464 KB Output is correct
21 Correct 15 ms 2632 KB Output is correct
22 Correct 29 ms 2660 KB Output is correct
23 Correct 24 ms 2808 KB Output is correct
24 Correct 24 ms 2808 KB Output is correct
25 Correct 25 ms 2808 KB Output is correct
26 Correct 23 ms 2808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 14768 KB Output is correct
2 Correct 837 ms 14784 KB Output is correct
3 Correct 810 ms 14784 KB Output is correct
4 Correct 839 ms 14784 KB Output is correct
5 Correct 981 ms 14784 KB Output is correct
6 Correct 1218 ms 14784 KB Output is correct
7 Correct 1043 ms 14784 KB Output is correct
8 Correct 990 ms 14784 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14784 KB Output is correct
2 Correct 482 ms 14784 KB Output is correct
3 Correct 1698 ms 22780 KB Output is correct
4 Correct 1796 ms 30888 KB Output is correct
5 Correct 1539 ms 38628 KB Output is correct
6 Correct 682 ms 38628 KB Output is correct
7 Correct 334 ms 38628 KB Output is correct
8 Correct 67 ms 38628 KB Output is correct
9 Correct 1746 ms 54092 KB Output is correct
10 Correct 1496 ms 62504 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 62504 KB Output is correct
2 Correct 1436 ms 69580 KB Output is correct
3 Correct 552 ms 77640 KB Output is correct
4 Correct 1220 ms 85452 KB Output is correct
5 Correct 1168 ms 93080 KB Output is correct
6 Correct 581 ms 100884 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1740 KB Output is correct
5 Correct 4 ms 1756 KB Output is correct
6 Correct 6 ms 1808 KB Output is correct
7 Correct 5 ms 1948 KB Output is correct
8 Correct 4 ms 1948 KB Output is correct
9 Correct 5 ms 1948 KB Output is correct
10 Correct 5 ms 1948 KB Output is correct
11 Correct 5 ms 1948 KB Output is correct
12 Correct 6 ms 1948 KB Output is correct
13 Correct 7 ms 1948 KB Output is correct
14 Correct 5 ms 1948 KB Output is correct
15 Correct 6 ms 1948 KB Output is correct
16 Correct 7 ms 1948 KB Output is correct
17 Correct 6 ms 1948 KB Output is correct
18 Correct 6 ms 1948 KB Output is correct
19 Correct 15 ms 2312 KB Output is correct
20 Correct 13 ms 2464 KB Output is correct
21 Correct 15 ms 2632 KB Output is correct
22 Correct 29 ms 2660 KB Output is correct
23 Correct 24 ms 2808 KB Output is correct
24 Correct 24 ms 2808 KB Output is correct
25 Correct 25 ms 2808 KB Output is correct
26 Correct 23 ms 2808 KB Output is correct
27 Correct 32 ms 100884 KB Output is correct
28 Correct 24 ms 100884 KB Output is correct
29 Correct 32 ms 100884 KB Output is correct
30 Correct 43 ms 100884 KB Output is correct
31 Correct 42 ms 100884 KB Output is correct
32 Correct 64 ms 100884 KB Output is correct
33 Correct 289 ms 100884 KB Output is correct
34 Correct 255 ms 101608 KB Output is correct
35 Correct 251 ms 104564 KB Output is correct
36 Correct 464 ms 107212 KB Output is correct
37 Correct 468 ms 109824 KB Output is correct
38 Correct 527 ms 112408 KB Output is correct
39 Correct 360 ms 113504 KB Output is correct
40 Correct 351 ms 114612 KB Output is correct
41 Correct 378 ms 115776 KB Output is correct
42 Correct 251 ms 117232 KB Output is correct
43 Correct 320 ms 119932 KB Output is correct
44 Correct 325 ms 122536 KB Output is correct
45 Correct 317 ms 125276 KB Output is correct
46 Correct 337 ms 127744 KB Output is correct
47 Correct 330 ms 130412 KB Output is correct
48 Correct 322 ms 133000 KB Output is correct
49 Correct 330 ms 135736 KB Output is correct
50 Correct 306 ms 138256 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1740 KB Output is correct
5 Correct 4 ms 1756 KB Output is correct
6 Correct 6 ms 1808 KB Output is correct
7 Correct 5 ms 1948 KB Output is correct
8 Correct 4 ms 1948 KB Output is correct
9 Correct 5 ms 1948 KB Output is correct
10 Correct 5 ms 1948 KB Output is correct
11 Correct 5 ms 1948 KB Output is correct
12 Correct 6 ms 1948 KB Output is correct
13 Correct 7 ms 1948 KB Output is correct
14 Correct 5 ms 1948 KB Output is correct
15 Correct 6 ms 1948 KB Output is correct
16 Correct 7 ms 1948 KB Output is correct
17 Correct 6 ms 1948 KB Output is correct
18 Correct 6 ms 1948 KB Output is correct
19 Correct 15 ms 2312 KB Output is correct
20 Correct 13 ms 2464 KB Output is correct
21 Correct 15 ms 2632 KB Output is correct
22 Correct 29 ms 2660 KB Output is correct
23 Correct 24 ms 2808 KB Output is correct
24 Correct 24 ms 2808 KB Output is correct
25 Correct 25 ms 2808 KB Output is correct
26 Correct 23 ms 2808 KB Output is correct
27 Correct 763 ms 14768 KB Output is correct
28 Correct 837 ms 14784 KB Output is correct
29 Correct 810 ms 14784 KB Output is correct
30 Correct 839 ms 14784 KB Output is correct
31 Correct 981 ms 14784 KB Output is correct
32 Correct 1218 ms 14784 KB Output is correct
33 Correct 1043 ms 14784 KB Output is correct
34 Correct 990 ms 14784 KB Output is correct
35 Correct 5 ms 14784 KB Output is correct
36 Correct 482 ms 14784 KB Output is correct
37 Correct 1698 ms 22780 KB Output is correct
38 Correct 1796 ms 30888 KB Output is correct
39 Correct 1539 ms 38628 KB Output is correct
40 Correct 682 ms 38628 KB Output is correct
41 Correct 334 ms 38628 KB Output is correct
42 Correct 67 ms 38628 KB Output is correct
43 Correct 1746 ms 54092 KB Output is correct
44 Correct 1496 ms 62504 KB Output is correct
45 Correct 1061 ms 62504 KB Output is correct
46 Correct 1436 ms 69580 KB Output is correct
47 Correct 552 ms 77640 KB Output is correct
48 Correct 1220 ms 85452 KB Output is correct
49 Correct 1168 ms 93080 KB Output is correct
50 Correct 581 ms 100884 KB Output is correct
51 Correct 32 ms 100884 KB Output is correct
52 Correct 24 ms 100884 KB Output is correct
53 Correct 32 ms 100884 KB Output is correct
54 Correct 43 ms 100884 KB Output is correct
55 Correct 42 ms 100884 KB Output is correct
56 Correct 64 ms 100884 KB Output is correct
57 Correct 289 ms 100884 KB Output is correct
58 Correct 255 ms 101608 KB Output is correct
59 Correct 251 ms 104564 KB Output is correct
60 Correct 464 ms 107212 KB Output is correct
61 Correct 468 ms 109824 KB Output is correct
62 Correct 527 ms 112408 KB Output is correct
63 Correct 360 ms 113504 KB Output is correct
64 Correct 351 ms 114612 KB Output is correct
65 Correct 378 ms 115776 KB Output is correct
66 Correct 251 ms 117232 KB Output is correct
67 Correct 320 ms 119932 KB Output is correct
68 Correct 325 ms 122536 KB Output is correct
69 Correct 317 ms 125276 KB Output is correct
70 Correct 337 ms 127744 KB Output is correct
71 Correct 330 ms 130412 KB Output is correct
72 Correct 322 ms 133000 KB Output is correct
73 Correct 330 ms 135736 KB Output is correct
74 Correct 306 ms 138256 KB Output is correct
75 Correct 940 ms 155040 KB Output is correct
76 Correct 904 ms 164188 KB Output is correct
77 Correct 1012 ms 172996 KB Output is correct
78 Correct 896 ms 181760 KB Output is correct
79 Correct 984 ms 190636 KB Output is correct
80 Correct 1033 ms 199528 KB Output is correct
81 Correct 1658 ms 207788 KB Output is correct
82 Correct 1777 ms 215604 KB Output is correct
83 Correct 1784 ms 223452 KB Output is correct
84 Correct 1938 ms 231836 KB Output is correct
85 Correct 1762 ms 239744 KB Output is correct
86 Correct 1743 ms 247736 KB Output is correct
87 Correct 1861 ms 255792 KB Output is correct
88 Correct 1286 ms 258964 KB Output is correct
89 Correct 1284 ms 262456 KB Output is correct
90 Correct 1219 ms 265636 KB Output is correct
91 Correct 1168 ms 269080 KB Output is correct
92 Correct 1212 ms 272532 KB Output is correct
93 Correct 1453 ms 279688 KB Output is correct
94 Correct 1391 ms 287072 KB Output is correct
95 Correct 1529 ms 293916 KB Output is correct
96 Correct 1469 ms 300900 KB Output is correct
97 Correct 1598 ms 307744 KB Output is correct
98 Correct 1234 ms 315244 KB Output is correct
99 Correct 1472 ms 322316 KB Output is correct
100 Correct 1588 ms 329032 KB Output is correct
101 Correct 1446 ms 336344 KB Output is correct
102 Correct 1444 ms 343280 KB Output is correct
103 Correct 1499 ms 350288 KB Output is correct
104 Correct 1474 ms 357056 KB Output is correct
105 Correct 879 ms 361876 KB Output is correct
106 Correct 1018 ms 369804 KB Output is correct
107 Correct 991 ms 377476 KB Output is correct
108 Correct 1062 ms 385248 KB Output is correct
109 Correct 940 ms 393148 KB Output is correct
110 Correct 1029 ms 400936 KB Output is correct
111 Correct 1006 ms 408624 KB Output is correct
112 Correct 983 ms 416488 KB Output is correct
113 Correct 1072 ms 424264 KB Output is correct
114 Correct 984 ms 432044 KB Output is correct
115 Correct 949 ms 439844 KB Output is correct
116 Correct 1006 ms 447580 KB Output is correct