oj.uz

Submission #252094

# Submission time Handle Problem Language Result Execution time Memory
252094 2020-07-24T06:24:31 Z Mlxa Circle selection (APIO18_circle_selection) C++14
100 / 100
 2658 ms 48328 KB 
#include <bits/stdc++.h>
using ll = long long;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
using namespace std;

const int N = 3e5 + 5;
int n;
int x[N];
int y[N];
int r[N];
int a[N];
int step = 30;
vector<int> desc;

ll sq(int t) {
    return (ll)t * t;
}
bool cross(int i, int j) {
    return sq(x[i] - x[j]) + sq(y[i] - y[j]) <= sq(r[i] + r[j]);
}

pair<int, int> id(int xi, int yi) {
    return {(xi >> step), (yi >> step)};
}
map<pair<int, int>, vector<int>> table;

void build() {
    table.clear();
    for (int i = 0; i < n; ++i) {
        if (a[i] == -1) {
            table[id(x[i], y[i])].push_back(i);
        }
    }
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif // LC
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> r[i];
        a[i] = -1;
        desc.push_back(i);
    }
    sort(all(desc), [&](int i, int j) {
         return mp(-r[i], i) < mp(-r[j], j);
    });
    build();
    for (int i : desc) {
        if (a[i] != -1) {
            continue;
        }
        assert((1 << step) >= r[i]);
        if ((1 << step) >= 2 * r[i]) {
            while ((1 << step) >= 2 * r[i]) {
                --step;
            }
            build();
        }
        int k = (step == 30 ? 1 : 2);
        for (int di = -k; di <= +k; ++di) {
            for (int dj = -k; dj <= +k; ++dj) {
                int dx = di << step;
                int dy = dj << step;
                pair<int, int> v = id(x[i] + dx, y[i] + dy);
                if (!table.count(v)) {
                    continue;
                }
                vector<int> tmp;
                for (int j : table[v]) {
                    if (cross(i, j)) {
                        assert(a[j] == -1);
                        a[j] = i;
                    } else {
                        tmp.push_back(j);
                    }
                }
                table[v] = tmp;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i] + 1 << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 8512 KB Output is correct
2 Correct 189 ms 9196 KB Output is correct
3 Correct 190 ms 10108 KB Output is correct
4 Correct 178 ms 8488 KB Output is correct
5 Correct 241 ms 15252 KB Output is correct
6 Correct 814 ms 25672 KB Output is correct
7 Correct 296 ms 16204 KB Output is correct
8 Correct 410 ms 18512 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 388 KB Output is correct
2 Correct 625 ms 13816 KB Output is correct
3 Correct 2149 ms 41172 KB Output is correct
4 Correct 2170 ms 41172 KB Output is correct
5 Correct 2324 ms 35804 KB Output is correct
6 Correct 751 ms 17528 KB Output is correct
7 Correct 278 ms 9416 KB Output is correct
8 Correct 37 ms 2296 KB Output is correct
9 Correct 2447 ms 40016 KB Output is correct
10 Correct 1895 ms 39404 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1831 ms 41248 KB Output is correct
2 Correct 1251 ms 41064 KB Output is correct
3 Correct 617 ms 16036 KB Output is correct
4 Correct 1276 ms 41124 KB Output is correct
5 Correct 1242 ms 41084 KB Output is correct
6 Correct 271 ms 10740 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 15 ms 1152 KB Output is correct
23 Correct 17 ms 1152 KB Output is correct
24 Correct 15 ms 1152 KB Output is correct
25 Correct 14 ms 1152 KB Output is correct
26 Correct 15 ms 1152 KB Output is correct
27 Correct 7 ms 1024 KB Output is correct
28 Correct 7 ms 1024 KB Output is correct
29 Correct 7 ms 1024 KB Output is correct
30 Correct 34 ms 1920 KB Output is correct
31 Correct 34 ms 1920 KB Output is correct
32 Correct 32 ms 1920 KB Output is correct
33 Correct 72 ms 6516 KB Output is correct
34 Correct 70 ms 6516 KB Output is correct
35 Correct 75 ms 6640 KB Output is correct
36 Correct 501 ms 16484 KB Output is correct
37 Correct 503 ms 16620 KB Output is correct
38 Correct 593 ms 16744 KB Output is correct
39 Correct 425 ms 13416 KB Output is correct
40 Correct 393 ms 13392 KB Output is correct
41 Correct 385 ms 13440 KB Output is correct
42 Correct 314 ms 11256 KB Output is correct
43 Correct 317 ms 16276 KB Output is correct
44 Correct 322 ms 16372 KB Output is correct
45 Correct 315 ms 16272 KB Output is correct
46 Correct 325 ms 16260 KB Output is correct
47 Correct 314 ms 16316 KB Output is correct
48 Correct 330 ms 16252 KB Output is correct
49 Correct 323 ms 16252 KB Output is correct
50 Correct 319 ms 16300 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 15 ms 1152 KB Output is correct
23 Correct 17 ms 1152 KB Output is correct
24 Correct 15 ms 1152 KB Output is correct
25 Correct 14 ms 1152 KB Output is correct
26 Correct 15 ms 1152 KB Output is correct
27 Correct 182 ms 8512 KB Output is correct
28 Correct 189 ms 9196 KB Output is correct
29 Correct 190 ms 10108 KB Output is correct
30 Correct 178 ms 8488 KB Output is correct
31 Correct 241 ms 15252 KB Output is correct
32 Correct 814 ms 25672 KB Output is correct
33 Correct 296 ms 16204 KB Output is correct
34 Correct 410 ms 18512 KB Output is correct
35 Correct 0 ms 388 KB Output is correct
36 Correct 625 ms 13816 KB Output is correct
37 Correct 2149 ms 41172 KB Output is correct
38 Correct 2170 ms 41172 KB Output is correct
39 Correct 2324 ms 35804 KB Output is correct
40 Correct 751 ms 17528 KB Output is correct
41 Correct 278 ms 9416 KB Output is correct
42 Correct 37 ms 2296 KB Output is correct
43 Correct 2447 ms 40016 KB Output is correct
44 Correct 1895 ms 39404 KB Output is correct
45 Correct 1831 ms 41248 KB Output is correct
46 Correct 1251 ms 41064 KB Output is correct
47 Correct 617 ms 16036 KB Output is correct
48 Correct 1276 ms 41124 KB Output is correct
49 Correct 1242 ms 41084 KB Output is correct
50 Correct 271 ms 10740 KB Output is correct
51 Correct 7 ms 1024 KB Output is correct
52 Correct 7 ms 1024 KB Output is correct
53 Correct 7 ms 1024 KB Output is correct
54 Correct 34 ms 1920 KB Output is correct
55 Correct 34 ms 1920 KB Output is correct
56 Correct 32 ms 1920 KB Output is correct
57 Correct 72 ms 6516 KB Output is correct
58 Correct 70 ms 6516 KB Output is correct
59 Correct 75 ms 6640 KB Output is correct
60 Correct 501 ms 16484 KB Output is correct
61 Correct 503 ms 16620 KB Output is correct
62 Correct 593 ms 16744 KB Output is correct
63 Correct 425 ms 13416 KB Output is correct
64 Correct 393 ms 13392 KB Output is correct
65 Correct 385 ms 13440 KB Output is correct
66 Correct 314 ms 11256 KB Output is correct
67 Correct 317 ms 16276 KB Output is correct
68 Correct 322 ms 16372 KB Output is correct
69 Correct 315 ms 16272 KB Output is correct
70 Correct 325 ms 16260 KB Output is correct
71 Correct 314 ms 16316 KB Output is correct
72 Correct 330 ms 16252 KB Output is correct
73 Correct 323 ms 16252 KB Output is correct
74 Correct 319 ms 16300 KB Output is correct
75 Correct 232 ms 10256 KB Output is correct
76 Correct 213 ms 10572 KB Output is correct
77 Correct 221 ms 11596 KB Output is correct
78 Correct 209 ms 9320 KB Output is correct
79 Correct 263 ms 10252 KB Output is correct
80 Correct 224 ms 9388 KB Output is correct
81 Correct 2382 ms 41096 KB Output is correct
82 Correct 1939 ms 41056 KB Output is correct
83 Correct 2028 ms 41200 KB Output is correct
84 Correct 2300 ms 41008 KB Output is correct
85 Correct 2062 ms 41056 KB Output is correct
86 Correct 1942 ms 41160 KB Output is correct
87 Correct 2488 ms 40796 KB Output is correct
88 Correct 1504 ms 39680 KB Output is correct
89 Correct 1569 ms 39472 KB Output is correct
90 Correct 1469 ms 39660 KB Output is correct
91 Correct 1474 ms 39624 KB Output is correct
92 Correct 1476 ms 39600 KB Output is correct
93 Correct 1712 ms 48076 KB Output is correct
94 Correct 1650 ms 48328 KB Output is correct
95 Correct 1685 ms 48076 KB Output is correct
96 Correct 1492 ms 48124 KB Output is correct
97 Correct 2508 ms 47904 KB Output is correct
98 Correct 1082 ms 31440 KB Output is correct
99 Correct 1638 ms 48160 KB Output is correct
100 Correct 1410 ms 47936 KB Output is correct
101 Correct 1534 ms 36940 KB Output is correct
102 Correct 1531 ms 47436 KB Output is correct
103 Correct 2658 ms 46684 KB Output is correct
104 Correct 1524 ms 47828 KB Output is correct
105 Correct 1246 ms 33108 KB Output is correct
106 Correct 1139 ms 46652 KB Output is correct
107 Correct 1197 ms 46668 KB Output is correct
108 Correct 1157 ms 46624 KB Output is correct
109 Correct 1205 ms 46608 KB Output is correct
110 Correct 1131 ms 46636 KB Output is correct
111 Correct 1156 ms 46692 KB Output is correct
112 Correct 1135 ms 46728 KB Output is correct
113 Correct 1134 ms 46744 KB Output is correct
114 Correct 1137 ms 46696 KB Output is correct
115 Correct 1186 ms 46748 KB Output is correct
116 Correct 1086 ms 46640 KB Output is correct