Submission #430572

#	Time	Username	Problem	Language	Result	Execution time	Memory
430572		Yarie	Circle selection (APIO18_circle_selection)	C++14	42 / 100	2839 ms	128712 KiB

circle_selection

#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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13