oj.uz

Submission #107874

# Submission time Handle Problem Language Result Execution time Memory
107874 2019-04-26T05:23:52 Z kuroni Circle selection (APIO18_circle_selection) C++17
100 / 100
 2241 ms 43728 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int N = 300005, MX = 1E9, INF = 2E9 + 7;

int n, cur = INF, ans[N], ind[N];
unordered_map<long long, vector<int>> gri;

long long sqr(long long u)
{
    return u * u;
}

struct SCircle
{
    int x, y, r;

    bool intersect(SCircle oth)
    {
        return sqr(oth.x - x) + sqr(oth.y - y) <= sqr(oth.r + r);
    }
} a[N];

void make_grid(int sz)
{
    gri.clear();
    for (int i = 1; i <= n; i++)
        if (ans[i] == 0)
        {
            int cx = a[i].x / sz, cy = a[i].y / sz;
            long long pos = 1LL * cx * INF + cy;
            gri[pos].push_back(i);
        }
}

void solve(long long pos, int u)
{
    if (gri.count(pos) == 0)
        return;
    vector<int> &cur = gri[pos];
    for (int i = 0; i < cur.size(); i++)
        if (a[cur[i]].intersect(a[u]))
        {
            ans[cur[i]] = u;
            swap(cur[i--], cur.back());
            cur.pop_back();
        }
    if (cur.empty())
        gri.erase(pos);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
        a[i].x += MX; a[i].y += MX;
        ind[i] = i;
    }
    sort(ind + 1, ind + n + 1, [](const int &x, const int &y) {
        return a[x].r > a[y].r || (a[x].r == a[y].r && x < y);
    });
    for (int i = 1; i <= n; i++)
    {
        int u = ind[i];
        if (ans[u] == 0)
        {
            if (a[u].r <= cur / 2)
            {
                cur = a[u].r;
                make_grid(cur);
            }
            for (int cx = a[u].x / cur - 2; cx <= a[u].x / cur + 2; cx++)
                for (int cy = a[u].y / cur - 2; cy <= a[u].y / cur + 2; cy++)
                    solve(1LL * cx * INF + cy, u);
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
}

Compilation message

circle_selection.cpp: In function 'void solve(long long int, int)':
circle_selection.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < cur.size(); i++)
                     ~~^~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 9 ms 640 KB Output is correct
21 Correct 6 ms 512 KB Output is correct
22 Correct 12 ms 1024 KB Output is correct
23 Correct 16 ms 1024 KB Output is correct
24 Correct 13 ms 896 KB Output is correct
25 Correct 12 ms 896 KB Output is correct
26 Correct 13 ms 1024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 15148 KB Output is correct
2 Correct 188 ms 15020 KB Output is correct
3 Correct 237 ms 14884 KB Output is correct
4 Correct 223 ms 15532 KB Output is correct
5 Correct 228 ms 13532 KB Output is correct
6 Correct 827 ms 25992 KB Output is correct
7 Correct 266 ms 15432 KB Output is correct
8 Correct 481 ms 18256 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 695 ms 14256 KB Output is correct
3 Correct 2058 ms 43276 KB Output is correct
4 Correct 1752 ms 43524 KB Output is correct
5 Correct 1709 ms 38564 KB Output is correct
6 Correct 628 ms 19384 KB Output is correct
7 Correct 207 ms 10512 KB Output is correct
8 Correct 29 ms 2560 KB Output is correct
9 Correct 2021 ms 42728 KB Output is correct
10 Correct 1322 ms 38164 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1472 ms 43116 KB Output is correct
2 Correct 1317 ms 42260 KB Output is correct
3 Correct 394 ms 24456 KB Output is correct
4 Correct 1548 ms 42600 KB Output is correct
5 Correct 1637 ms 42848 KB Output is correct
6 Correct 338 ms 18424 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 9 ms 640 KB Output is correct
21 Correct 6 ms 512 KB Output is correct
22 Correct 12 ms 1024 KB Output is correct
23 Correct 16 ms 1024 KB Output is correct
24 Correct 13 ms 896 KB Output is correct
25 Correct 12 ms 896 KB Output is correct
26 Correct 13 ms 1024 KB Output is correct
27 Correct 11 ms 896 KB Output is correct
28 Correct 10 ms 896 KB Output is correct
29 Correct 10 ms 896 KB Output is correct
30 Correct 33 ms 1664 KB Output is correct
31 Correct 34 ms 1664 KB Output is correct
32 Correct 30 ms 1716 KB Output is correct
33 Correct 83 ms 6264 KB Output is correct
34 Correct 81 ms 6120 KB Output is correct
35 Correct 84 ms 5940 KB Output is correct
36 Correct 436 ms 14184 KB Output is correct
37 Correct 588 ms 14160 KB Output is correct
38 Correct 441 ms 14268 KB Output is correct
39 Correct 260 ms 11388 KB Output is correct
40 Correct 322 ms 11436 KB Output is correct
41 Correct 329 ms 11424 KB Output is correct
42 Correct 240 ms 13112 KB Output is correct
43 Correct 391 ms 14056 KB Output is correct
44 Correct 510 ms 13992 KB Output is correct
45 Correct 402 ms 14068 KB Output is correct
46 Correct 457 ms 14088 KB Output is correct
47 Correct 324 ms 14020 KB Output is correct
48 Correct 454 ms 13960 KB Output is correct
49 Correct 496 ms 14008 KB Output is correct
50 Correct 535 ms 14148 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 9 ms 640 KB Output is correct
21 Correct 6 ms 512 KB Output is correct
22 Correct 12 ms 1024 KB Output is correct
23 Correct 16 ms 1024 KB Output is correct
24 Correct 13 ms 896 KB Output is correct
25 Correct 12 ms 896 KB Output is correct
26 Correct 13 ms 1024 KB Output is correct
27 Correct 206 ms 15148 KB Output is correct
28 Correct 188 ms 15020 KB Output is correct
29 Correct 237 ms 14884 KB Output is correct
30 Correct 223 ms 15532 KB Output is correct
31 Correct 228 ms 13532 KB Output is correct
32 Correct 827 ms 25992 KB Output is correct
33 Correct 266 ms 15432 KB Output is correct
34 Correct 481 ms 18256 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 695 ms 14256 KB Output is correct
37 Correct 2058 ms 43276 KB Output is correct
38 Correct 1752 ms 43524 KB Output is correct
39 Correct 1709 ms 38564 KB Output is correct
40 Correct 628 ms 19384 KB Output is correct
41 Correct 207 ms 10512 KB Output is correct
42 Correct 29 ms 2560 KB Output is correct
43 Correct 2021 ms 42728 KB Output is correct
44 Correct 1322 ms 38164 KB Output is correct
45 Correct 1472 ms 43116 KB Output is correct
46 Correct 1317 ms 42260 KB Output is correct
47 Correct 394 ms 24456 KB Output is correct
48 Correct 1548 ms 42600 KB Output is correct
49 Correct 1637 ms 42848 KB Output is correct
50 Correct 338 ms 18424 KB Output is correct
51 Correct 11 ms 896 KB Output is correct
52 Correct 10 ms 896 KB Output is correct
53 Correct 10 ms 896 KB Output is correct
54 Correct 33 ms 1664 KB Output is correct
55 Correct 34 ms 1664 KB Output is correct
56 Correct 30 ms 1716 KB Output is correct
57 Correct 83 ms 6264 KB Output is correct
58 Correct 81 ms 6120 KB Output is correct
59 Correct 84 ms 5940 KB Output is correct
60 Correct 436 ms 14184 KB Output is correct
61 Correct 588 ms 14160 KB Output is correct
62 Correct 441 ms 14268 KB Output is correct
63 Correct 260 ms 11388 KB Output is correct
64 Correct 322 ms 11436 KB Output is correct
65 Correct 329 ms 11424 KB Output is correct
66 Correct 240 ms 13112 KB Output is correct
67 Correct 391 ms 14056 KB Output is correct
68 Correct 510 ms 13992 KB Output is correct
69 Correct 402 ms 14068 KB Output is correct
70 Correct 457 ms 14088 KB Output is correct
71 Correct 324 ms 14020 KB Output is correct
72 Correct 454 ms 13960 KB Output is correct
73 Correct 496 ms 14008 KB Output is correct
74 Correct 535 ms 14148 KB Output is correct
75 Correct 283 ms 18068 KB Output is correct
76 Correct 263 ms 17384 KB Output is correct
77 Correct 256 ms 17332 KB Output is correct
78 Correct 272 ms 17240 KB Output is correct
79 Correct 320 ms 17112 KB Output is correct
80 Correct 252 ms 17084 KB Output is correct
81 Correct 1906 ms 43200 KB Output is correct
82 Correct 2056 ms 43100 KB Output is correct
83 Correct 2076 ms 43040 KB Output is correct
84 Correct 2241 ms 43728 KB Output is correct
85 Correct 2088 ms 43176 KB Output is correct
86 Correct 1939 ms 43144 KB Output is correct
87 Correct 1990 ms 43140 KB Output is correct
88 Correct 1202 ms 35056 KB Output is correct
89 Correct 1165 ms 35116 KB Output is correct
90 Correct 1111 ms 35076 KB Output is correct
91 Correct 1091 ms 34896 KB Output is correct
92 Correct 1183 ms 34944 KB Output is correct
93 Correct 1899 ms 42116 KB Output is correct
94 Correct 1980 ms 42416 KB Output is correct
95 Correct 2113 ms 42116 KB Output is correct
96 Correct 1784 ms 42088 KB Output is correct
97 Correct 2155 ms 42116 KB Output is correct
98 Correct 1160 ms 32104 KB Output is correct
99 Correct 2081 ms 42432 KB Output is correct
100 Correct 2054 ms 42024 KB Output is correct
101 Correct 1519 ms 37648 KB Output is correct
102 Correct 1777 ms 42032 KB Output is correct
103 Correct 1718 ms 41864 KB Output is correct
104 Correct 1750 ms 42056 KB Output is correct
105 Correct 1044 ms 40020 KB Output is correct
106 Correct 1306 ms 41224 KB Output is correct
107 Correct 1447 ms 41452 KB Output is correct
108 Correct 1303 ms 41516 KB Output is correct
109 Correct 1201 ms 41476 KB Output is correct
110 Correct 1362 ms 41344 KB Output is correct
111 Correct 1306 ms 41328 KB Output is correct
112 Correct 1496 ms 41476 KB Output is correct
113 Correct 1308 ms 41488 KB Output is correct
114 Correct 1353 ms 41252 KB Output is correct
115 Correct 1261 ms 41316 KB Output is correct
116 Correct 1363 ms 41348 KB Output is correct