oj.uz

Submission #252080

# Submission time Handle Problem Language Result Execution time Memory
252080 2020-07-24T06:02:41 Z Mlxa Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 45588 KB 
#include <bits/stdc++.h>
using ll = long long;
#define int ll
#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 = 32;
vector<int> desc;

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

int id(int xi, int yi) {
    return ((xi >> step) << 16)^ (yi >> step);
}
map<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);
    });
    for (int i : desc) {
        if (a[i] != -1) {
            continue;
        }
        assert((1LL << step) >= 2 * r[i]);
        while ((1LL << step) >= 4 * r[i]) {
            --step;
            build();
        }
        int delta = 1LL << step;
        for (int dx = -delta; dx <= +delta; dx += delta) {
            for (int dy = -delta; dy <= +delta; dy += delta) {
                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 0 ms 384 KB Output is correct
8 Correct 1 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 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 7 ms 640 KB Output is correct
22 Correct 20 ms 1152 KB Output is correct
23 Correct 33 ms 1152 KB Output is correct
24 Correct 20 ms 1152 KB Output is correct
25 Correct 25 ms 1152 KB Output is correct
26 Correct 22 ms 1152 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 16992 KB Output is correct
2 Correct 194 ms 19028 KB Output is correct
3 Correct 198 ms 17720 KB Output is correct
4 Correct 192 ms 15840 KB Output is correct
5 Correct 472 ms 19036 KB Output is correct
6 Correct 1080 ms 24132 KB Output is correct
7 Correct 505 ms 20112 KB Output is correct
8 Correct 644 ms 20228 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 694 ms 15948 KB Output is correct
3 Execution timed out 3083 ms 45328 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 45588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 0 ms 384 KB Output is correct
8 Correct 1 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 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 7 ms 640 KB Output is correct
22 Correct 20 ms 1152 KB Output is correct
23 Correct 33 ms 1152 KB Output is correct
24 Correct 20 ms 1152 KB Output is correct
25 Correct 25 ms 1152 KB Output is correct
26 Correct 22 ms 1152 KB Output is correct
27 Correct 8 ms 1136 KB Output is correct
28 Correct 10 ms 1024 KB Output is correct
29 Correct 9 ms 1024 KB Output is correct
30 Correct 44 ms 1968 KB Output is correct
31 Correct 46 ms 1972 KB Output is correct
32 Correct 47 ms 1920 KB Output is correct
33 Correct 68 ms 5872 KB Output is correct
34 Correct 79 ms 5872 KB Output is correct
35 Correct 75 ms 6112 KB Output is correct
36 Correct 937 ms 16136 KB Output is correct
37 Correct 956 ms 16064 KB Output is correct
38 Correct 909 ms 16072 KB Output is correct
39 Correct 472 ms 11328 KB Output is correct
40 Correct 371 ms 11192 KB Output is correct
41 Correct 383 ms 11292 KB Output is correct
42 Correct 223 ms 7912 KB Output is correct
43 Correct 672 ms 15584 KB Output is correct
44 Correct 765 ms 15584 KB Output is correct
45 Correct 676 ms 15468 KB Output is correct
46 Correct 693 ms 15556 KB Output is correct
47 Correct 677 ms 15584 KB Output is correct
48 Correct 751 ms 15552 KB Output is correct
49 Correct 849 ms 15640 KB Output is correct
50 Correct 687 ms 15528 KB Output is correct

Subtask #6
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 0 ms 384 KB Output is correct
8 Correct 1 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 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 7 ms 640 KB Output is correct
22 Correct 20 ms 1152 KB Output is correct
23 Correct 33 ms 1152 KB Output is correct
24 Correct 20 ms 1152 KB Output is correct
25 Correct 25 ms 1152 KB Output is correct
26 Correct 22 ms 1152 KB Output is correct
27 Correct 190 ms 16992 KB Output is correct
28 Correct 194 ms 19028 KB Output is correct
29 Correct 198 ms 17720 KB Output is correct
30 Correct 192 ms 15840 KB Output is correct
31 Correct 472 ms 19036 KB Output is correct
32 Correct 1080 ms 24132 KB Output is correct
33 Correct 505 ms 20112 KB Output is correct
34 Correct 644 ms 20228 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 694 ms 15948 KB Output is correct
37 Execution timed out 3083 ms 45328 KB Time limit exceeded
38 Halted 0 ms 0 KB -