oj.uz

Submission #430572

# Submission time Handle Problem Language Result Execution time Memory
430572 2021-06-16T16:11:00 Z Yarie Circle selection (APIO18_circle_selection) C++14
42 / 100
 2839 ms 128712 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

struct Circle{
    ll x, y, r;
    int ind;
};
bool operator<(Circle c1, Circle c2) {
    return c1.ind < c2.ind;
}

ll Dist(Circle c1, Circle c2) {
    return (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y);
}

bool inters(Circle c1, Circle c2) {
    return Dist(c1, c2) <= (c1.r + c2.r) * (c1.r + c2.r);
}

int main() {
    int n;
    cin >> n;
    vector<Circle> circles(n);
    set<pii> ranges;
    vector<pair<pii, int>> sweep;
    bool subtask2 = true;
    bool subtask4 = true;
    map<pii, set<Circle>> grid;
    ll r = 0;
    for (int i = 0; i < n; i++) {
        cin >> circles[i].x >> circles[i].y >> circles[i].r;
        circles[i].ind = i + 1;
        if (r && r != circles[i].r) {
            subtask4 = false;
        }
        r = circles[i].r;
        grid[{circles[i].x / r, circles[i].y / r}].insert(circles[i]);
        if (circles[i].y) subtask2 = false;
        sweep.push_back({{circles[i].x, circles[i].y - circles[i].r}, i});
        sweep.push_back({{circles[i].x, circles[i].y + circles[i].r}, i});
        ranges.insert({circles[i].x - circles[i].r, i + 1});
        ranges.insert({circles[i].x + circles[i].r, i + 1});
    }
    sort(all(circles), [] (Circle c1, Circle c2) {
        if (c1.r == c2.r) return c1.ind < c2.ind;
        return c1.r > c2.r;
    });
    vi ans(n + 1);
    if (subtask4) {
        for (auto c : circles) {
            if (ans[c.ind]) continue;
            int x = c.x / r - 2;
            int y = c.y / r - 2;
            for (int i = x; i < x + 5; i++) {
                for (int j = y; j < y + 5; j++) {
                    auto it1 = grid.find({i, j});
                    if (it1 == grid.end()) continue;
                    for (auto it = it1->y.begin(); it != it1->y.end();) {
                        if (inters(c, *it)) {
                            ans[it->ind] = c.ind;
                            it = it1->y.erase(it);
                        } else {
                            it++;
                        }
                    }
                }
            }
        }
    }
    if (n <= 5000) {
        sort(all(circles), [] (Circle c1, Circle c2) {
            if (c1.r == c2.r) return c1.ind < c2.ind;
            return c1.r > c2.r;
        });
        for (int i = 0; i < n; i++) {
            Circle c = circles[i];
            if (ans[c.ind]) continue;
            ans[c.ind] = c.ind;
            for (int j = i + 1; j < n; j++) {
                if (!ans[circles[j].ind] && inters(circles[j], c)) {
                    ans[circles[j].ind] = c.ind;
                }
            }
        }
        for (int i = 1; i <= n; i++) cout << (ans[i] ? ans[i] : i) << " ";
        return 0;
    }
    if (subtask2) {
        sort(all(circles), [] (Circle c1, Circle c2) {
            if (c1.r == c2.r) return c1.ind < c2.ind;
            return c1.r > c2.r;
        });
        for (auto c : circles) {
            if (ans[c.ind]) continue;
            ans[c.ind] = c.ind;
            for (auto it = ranges.lower_bound({c.x - c.r, 0}); it != ranges.end() && it->x <= c.x + c.r; it = ranges.erase(it)) {
                if (!ans[it->y]) {
                    ans[it->y] = c.ind;
                }
            }
        }
        for (int i = 1; i <= n; i++) cout << (ans[i] ? ans[i] : i) << " ";
        return 0;
    }
    sort(all(sweep), [&] (pair<pii, int> p1, pair<pii, int> p2) {
        if (p1.x.y == p2.x.y) {
            bool a, b;
            a = p1.x.y < circles[p1.y].y;
            b = p2.x.y < circles[p2.y].y;
            return a > b;
        }
        return p1.x.y < p2.x.y;
    });
    set<pii> inside;
    for (auto p : sweep) {
        if (ans[p.y + 1]) continue;
        auto it = inside.insert({p.x.x, p.y});
        auto before = it.x, after = it.x;
        if (before != inside.begin()) {
            before--;
            if (inters(circles[before->y], circles[p.y])) {
                if (circles[before->y].r > circles[p.y].r || (circles[before->y].r == circles[p.y].r && before->y < p.y)) {
                    ans[before->y + 1] = ans[p.y + 1] = before->y + 1;
                } else {
                    ans[before->y + 1] = ans[p.y + 1] = p.y + 1;
                }
                inside.erase(it.x), inside.erase(before);
                continue;
            }
        }
        after++;
        if (after != inside.end()) {
            if (inters(circles[after->y], circles[p.y])) {
                if (circles[after->y].r > circles[p.y].r || (circles[after->y].r == circles[p.y].r && after->y < p.y)) {
                    ans[after->y + 1] = ans[p.y + 1] = after->y + 1;
                } else {
                    ans[after->y + 1] = ans[p.y + 1] = p.y + 1;
                }
                inside.erase(it.x), inside.erase(after);
                continue;
            }
        }
        if (!it.y) {
            inside.erase(it.x);
        }
    }
    for (int i = 1; i <= n; i++) cout << (ans[i] ? ans[i] : i) << " ";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 3 ms 588 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 14 ms 1832 KB Output is correct
20 Correct 14 ms 1800 KB Output is correct
21 Correct 15 ms 1936 KB Output is correct
22 Correct 47 ms 2416 KB Output is correct
23 Correct 44 ms 2312 KB Output is correct
24 Correct 46 ms 2388 KB Output is correct
25 Correct 45 ms 2312 KB Output is correct
26 Correct 45 ms 2416 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1589 ms 95016 KB Output is correct
2 Correct 1605 ms 94876 KB Output is correct
3 Correct 1642 ms 94652 KB Output is correct
4 Correct 1531 ms 95012 KB Output is correct
5 Correct 1769 ms 119596 KB Output is correct
6 Correct 1666 ms 125284 KB Output is correct
7 Correct 1697 ms 124640 KB Output is correct
8 Correct 1678 ms 124924 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 504 ms 43152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2839 ms 128712 KB Output is correct
2 Correct 2081 ms 128080 KB Output is correct
3 Correct 1980 ms 105612 KB Output is correct
4 Correct 2217 ms 128312 KB Output is correct
5 Correct 2179 ms 128484 KB Output is correct
6 Correct 1896 ms 97664 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 3 ms 588 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 14 ms 1832 KB Output is correct
20 Correct 14 ms 1800 KB Output is correct
21 Correct 15 ms 1936 KB Output is correct
22 Correct 47 ms 2416 KB Output is correct
23 Correct 44 ms 2312 KB Output is correct
24 Correct 46 ms 2388 KB Output is correct
25 Correct 45 ms 2312 KB Output is correct
26 Correct 45 ms 2416 KB Output is correct
27 Incorrect 31 ms 3588 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 3 ms 588 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 14 ms 1832 KB Output is correct
20 Correct 14 ms 1800 KB Output is correct
21 Correct 15 ms 1936 KB Output is correct
22 Correct 47 ms 2416 KB Output is correct
23 Correct 44 ms 2312 KB Output is correct
24 Correct 46 ms 2388 KB Output is correct
25 Correct 45 ms 2312 KB Output is correct
26 Correct 45 ms 2416 KB Output is correct
27 Correct 1589 ms 95016 KB Output is correct
28 Correct 1605 ms 94876 KB Output is correct
29 Correct 1642 ms 94652 KB Output is correct
30 Correct 1531 ms 95012 KB Output is correct
31 Correct 1769 ms 119596 KB Output is correct
32 Correct 1666 ms 125284 KB Output is correct
33 Correct 1697 ms 124640 KB Output is correct
34 Correct 1678 ms 124924 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Incorrect 504 ms 43152 KB Output isn't correct
37 Halted 0 ms 0 KB -