oj.uz

Submission #366608

# Submission time Handle Problem Language Result Execution time Memory
366608 2021-02-14T19:27:57 Z valerikk Circle selection (APIO18_circle_selection) C++17
100 / 100
 1354 ms 114936 KB 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

struct Circle {
    ll x, y, r;
    int id;

    Circle() = default;
    
    Circle(ll x, ll y, ll r, int id) : x(x), y(y), r(r), id(id) {}
};

struct Point {
    ll y;
    int id;

    Point() = default;

    Point(ll y, int id) : y(y), id(id) {}
};

bool operator<(const Circle &a, const Circle &b) {
    return a.r > b.r || (a.r == b.r && a.id < b.id);
}

bool operator<(const Point &a, const Point &b) {
    return a.y < b.y;
}

template<class T>
T sqr(T x) {
    return x * x;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<Circle> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].r;
        c[i].id = i;
    }
    sort(c.begin(), c.end());

    auto intersect = [&](int i, int j)->bool {
        return sqr(c[i].x - c[j].x) + sqr(c[i].y - c[j].y) <= sqr(c[i].r + c[j].r);
    };

    ll R;
    vector<vector<Point>> points;

    vector<int> order_x(n);
    iota(order_x.begin(), order_x.end(), 0);
    sort(order_x.begin(), order_x.end(), [&](const int &i, const int &j) {
        return c[i].x < c[j].x;
    });
    vector<int> pos_x(n);
    vector<ll> sorted_x(n);
    for (int i = 0; i < n; i++) {
        pos_x[order_x[i]] = i;
        sorted_x[i] = c[order_x[i]].x;
    }

    vector<int> order_y(n);
    iota(order_y.begin(), order_y.end(), 0);
    sort(order_y.begin(), order_y.end(), [&](const int &i, const int &j) {
        return c[i].y < c[j].y;
    });
    vector<int> pos_y(n);
    vector<ll> sorted_y(n);
    for (int i = 0; i < n; i++) {
        pos_y[order_y[i]] = i;
        sorted_y[i] = c[order_y[i]].y;
    }

    vector<bool> used(n, false);

    int diff_x;
    vector<ll> scaled_x;
    vector<int> scaled_pos(n);
    auto do_rescaling = [&](ll R_) {
        R = R_;
        scaled_x.clear();
        scaled_x.push_back(sorted_x[0] / R);
        scaled_pos[order_x[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (sorted_x[i] / R != scaled_x.back())
                scaled_x.push_back(sorted_x[i] / R);
            scaled_pos[order_x[i]] = (int)scaled_x.size() - 1;
        }
        diff_x = scaled_x.size();
        points.resize(diff_x);
        for (auto& v: points) 
            v.clear();
        for (int i = 0; i < n; i++) {
            if (!used[order_y[i]]) 
                points[scaled_pos[order_y[i]]].emplace_back(sorted_y[i] / R, order_y[i]);
        }
        /*for (int i = 0; i < n; i++)
            assert(scaled_x[scaled_pos[i]] == c[i].x / R);*/
        /*for (int i = 0; i < diff_x; i++) {
            for (const auto& p : points[i]) {
                if (!(scaled_x[i] == c[p.id].x / R && p.y == c[p.id].y / R)) {
                    cout << i << " " << p.y << " " << c[p.id].id + 1 << "\n";
                }
            }
        }
        cout << endl;*/
    };

    vector<int> answer(n, -2);
    
    do_rescaling(c[0].r);

    for (int i = 0; i < n; i++) {
        if (2 * c[i].r <= R)
            do_rescaling(c[i].r);
        if (used[i])
            continue;
       
        int left_x = lower_bound(scaled_x.begin(), scaled_x.end(), scaled_x[scaled_pos[i]] - 2) - scaled_x.begin();
        int right_x = upper_bound(scaled_x.begin(), scaled_x.end(), scaled_x[scaled_pos[i]] + 2) - scaled_x.begin();
        for (int x = left_x; x < right_x; x++) {
            int left_y = lower_bound(points[x].begin(), points[x].end(), Point{c[i].y / R - 2, -1}) - points[x].begin();
            int right_y = upper_bound(points[x].begin(), points[x].end(), Point{c[i].y / R + 2, -1}) - points[x].begin();
            for (int y = left_y; y < right_y; y++) {
                if (!used[points[x][y].id] && intersect(i, points[x][y].id)) {
                    used[points[x][y].id] = true;
                    answer[c[points[x][y].id].id] = c[i].id;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) 
        cout << answer[i] + 1 << " ";
    cout << endl;
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 49812 KB Output is correct
2 Correct 337 ms 50104 KB Output is correct
3 Correct 377 ms 45876 KB Output is correct
4 Correct 301 ms 47304 KB Output is correct
5 Correct 312 ms 42536 KB Output is correct
6 Correct 432 ms 50772 KB Output is correct
7 Correct 361 ms 48532 KB Output is correct
8 Correct 383 ms 49432 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 178 ms 18440 KB Output is correct
3 Correct 697 ms 55736 KB Output is correct
4 Correct 690 ms 55896 KB Output is correct
5 Correct 624 ms 51968 KB Output is correct
6 Correct 267 ms 26732 KB Output is correct
7 Correct 121 ms 14912 KB Output is correct
8 Correct 22 ms 3360 KB Output is correct
9 Correct 654 ms 57012 KB Output is correct
10 Correct 585 ms 56328 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 41916 KB Output is correct
2 Correct 513 ms 49364 KB Output is correct
3 Correct 358 ms 38252 KB Output is correct
4 Correct 500 ms 48724 KB Output is correct
5 Correct 532 ms 49492 KB Output is correct
6 Correct 340 ms 37100 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 5 ms 1132 KB Output is correct
20 Correct 5 ms 1132 KB Output is correct
21 Correct 7 ms 1132 KB Output is correct
22 Correct 7 ms 1260 KB Output is correct
23 Correct 8 ms 1388 KB Output is correct
24 Correct 7 ms 1260 KB Output is correct
25 Correct 7 ms 1260 KB Output is correct
26 Correct 7 ms 1260 KB Output is correct
27 Correct 10 ms 2156 KB Output is correct
28 Correct 10 ms 1772 KB Output is correct
29 Correct 10 ms 2028 KB Output is correct
30 Correct 15 ms 2312 KB Output is correct
31 Correct 14 ms 2016 KB Output is correct
32 Correct 18 ms 2028 KB Output is correct
33 Correct 108 ms 13924 KB Output is correct
34 Correct 113 ms 17556 KB Output is correct
35 Correct 108 ms 15724 KB Output is correct
36 Correct 198 ms 17748 KB Output is correct
37 Correct 169 ms 17276 KB Output is correct
38 Correct 169 ms 18072 KB Output is correct
39 Correct 247 ms 38208 KB Output is correct
40 Correct 244 ms 38436 KB Output is correct
41 Correct 236 ms 36688 KB Output is correct
42 Correct 90 ms 12396 KB Output is correct
43 Correct 133 ms 16744 KB Output is correct
44 Correct 132 ms 16744 KB Output is correct
45 Correct 125 ms 16744 KB Output is correct
46 Correct 145 ms 16744 KB Output is correct
47 Correct 127 ms 16744 KB Output is correct
48 Correct 122 ms 16744 KB Output is correct
49 Correct 139 ms 16872 KB Output is correct
50 Correct 123 ms 16744 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 5 ms 1132 KB Output is correct
20 Correct 5 ms 1132 KB Output is correct
21 Correct 7 ms 1132 KB Output is correct
22 Correct 7 ms 1260 KB Output is correct
23 Correct 8 ms 1388 KB Output is correct
24 Correct 7 ms 1260 KB Output is correct
25 Correct 7 ms 1260 KB Output is correct
26 Correct 7 ms 1260 KB Output is correct
27 Correct 319 ms 49812 KB Output is correct
28 Correct 337 ms 50104 KB Output is correct
29 Correct 377 ms 45876 KB Output is correct
30 Correct 301 ms 47304 KB Output is correct
31 Correct 312 ms 42536 KB Output is correct
32 Correct 432 ms 50772 KB Output is correct
33 Correct 361 ms 48532 KB Output is correct
34 Correct 383 ms 49432 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 178 ms 18440 KB Output is correct
37 Correct 697 ms 55736 KB Output is correct
38 Correct 690 ms 55896 KB Output is correct
39 Correct 624 ms 51968 KB Output is correct
40 Correct 267 ms 26732 KB Output is correct
41 Correct 121 ms 14912 KB Output is correct
42 Correct 22 ms 3360 KB Output is correct
43 Correct 654 ms 57012 KB Output is correct
44 Correct 585 ms 56328 KB Output is correct
45 Correct 550 ms 41916 KB Output is correct
46 Correct 513 ms 49364 KB Output is correct
47 Correct 358 ms 38252 KB Output is correct
48 Correct 500 ms 48724 KB Output is correct
49 Correct 532 ms 49492 KB Output is correct
50 Correct 340 ms 37100 KB Output is correct
51 Correct 10 ms 2156 KB Output is correct
52 Correct 10 ms 1772 KB Output is correct
53 Correct 10 ms 2028 KB Output is correct
54 Correct 15 ms 2312 KB Output is correct
55 Correct 14 ms 2016 KB Output is correct
56 Correct 18 ms 2028 KB Output is correct
57 Correct 108 ms 13924 KB Output is correct
58 Correct 113 ms 17556 KB Output is correct
59 Correct 108 ms 15724 KB Output is correct
60 Correct 198 ms 17748 KB Output is correct
61 Correct 169 ms 17276 KB Output is correct
62 Correct 169 ms 18072 KB Output is correct
63 Correct 247 ms 38208 KB Output is correct
64 Correct 244 ms 38436 KB Output is correct
65 Correct 236 ms 36688 KB Output is correct
66 Correct 90 ms 12396 KB Output is correct
67 Correct 133 ms 16744 KB Output is correct
68 Correct 132 ms 16744 KB Output is correct
69 Correct 125 ms 16744 KB Output is correct
70 Correct 145 ms 16744 KB Output is correct
71 Correct 127 ms 16744 KB Output is correct
72 Correct 122 ms 16744 KB Output is correct
73 Correct 139 ms 16872 KB Output is correct
74 Correct 123 ms 16744 KB Output is correct
75 Correct 407 ms 48416 KB Output is correct
76 Correct 395 ms 45716 KB Output is correct
77 Correct 421 ms 44124 KB Output is correct
78 Correct 384 ms 46536 KB Output is correct
79 Correct 421 ms 45796 KB Output is correct
80 Correct 420 ms 42824 KB Output is correct
81 Correct 710 ms 51924 KB Output is correct
82 Correct 712 ms 57088 KB Output is correct
83 Correct 713 ms 56668 KB Output is correct
84 Correct 688 ms 56416 KB Output is correct
85 Correct 707 ms 53820 KB Output is correct
86 Correct 722 ms 51984 KB Output is correct
87 Correct 668 ms 55368 KB Output is correct
88 Correct 1321 ms 105796 KB Output is correct
89 Correct 1310 ms 110156 KB Output is correct
90 Correct 1354 ms 110184 KB Output is correct
91 Correct 1291 ms 110460 KB Output is correct
92 Correct 1281 ms 114936 KB Output is correct
93 Correct 599 ms 54100 KB Output is correct
94 Correct 469 ms 38984 KB Output is correct
95 Correct 577 ms 54228 KB Output is correct
96 Correct 616 ms 53864 KB Output is correct
97 Correct 637 ms 39660 KB Output is correct
98 Correct 538 ms 51628 KB Output is correct
99 Correct 598 ms 54356 KB Output is correct
100 Correct 561 ms 54260 KB Output is correct
101 Correct 570 ms 49536 KB Output is correct
102 Correct 606 ms 53988 KB Output is correct
103 Correct 622 ms 38384 KB Output is correct
104 Correct 623 ms 54100 KB Output is correct
105 Correct 365 ms 36896 KB Output is correct
106 Correct 493 ms 47068 KB Output is correct
107 Correct 490 ms 47096 KB Output is correct
108 Correct 451 ms 47056 KB Output is correct
109 Correct 486 ms 47068 KB Output is correct
110 Correct 506 ms 47084 KB Output is correct
111 Correct 475 ms 47016 KB Output is correct
112 Correct 442 ms 46940 KB Output is correct
113 Correct 503 ms 47196 KB Output is correct
114 Correct 467 ms 47196 KB Output is correct
115 Correct 443 ms 47196 KB Output is correct
116 Correct 473 ms 49044 KB Output is correct