Submission #1183227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183227		anmattroi	Circle selection (APIO18_circle_selection)	C++17	100 / 100	733 ms	60932 KiB

circle_selection

#include <bits/stdc++.h>
#define maxn 300005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, last = 0;
int ans[maxn];

struct circle {
    int x, y, r;
} a[maxn];

int intersect(int x, int y) {
    return (1LL * (a[x].x - a[y].x) * (a[x].x - a[y].x) + 1LL * (a[x].y - a[y].y) * (a[x].y - a[y].y))
            <= (1LL * (a[x].r + a[y].r) * (a[x].r + a[y].r));
}

namespace getNextCircleHelper {

    struct evilAndIntimidatingSet {
        int radius, index;
        evilAndIntimidatingSet() {}
        evilAndIntimidatingSet(int _radius, int _index) : radius(_radius), index(_index) {}

        bool operator < (const evilAndIntimidatingSet &other) const {
            if (radius != other.radius) return radius > other.radius;
            return index < other.index;
        }

    };

    set<evilAndIntimidatingSet> s;

    void init() {
        for (int i = 1; i <= n; i++) s.insert(evilAndIntimidatingSet(a[i].r, i));
    }


}

int getNextCircle() {
    if (getNextCircleHelper::s.empty()) return -1;
    return getNextCircleHelper::s.begin()->index;
}

void del(int elimd, int elim) {
    if (intersect(elimd, elim)) {
        getNextCircleHelper::s.erase(getNextCircleHelper::evilAndIntimidatingSet(a[elimd].r, elimd));
        ans[elimd] = elim;
    }
}

int c[maxn], n1 = 0;
vector<vector<ii> > rem;
vector<vector<int> > nex;

ii sortX[maxn], sortY[maxn];

int equivalenceClass[maxn];

int getNext(int i, int j) {
    return nex[i][j] == j ? j : nex[i][j] = getNext(i, nex[i][j]);
}

void rebuild(int newRadius) {
    n1 = 0; last = newRadius;
    for (int i = 1; i <= n; i++)
        if (ans[sortX[i].se] == 0) c[++n1] = sortX[i].fi/last;
    n1 = unique(c + 1, c + n1 + 1) - c - 1;

    for (int i = 1, it = 1; i <= n; i++) {
        if (ans[sortX[i].se] > 0) continue;
        while (it <= n1 && c[it] < sortX[i].fi/last) ++it;
        equivalenceClass[sortX[i].se] = it;
    }
    rem.clear(); nex.clear();
    rem.resize(n1+1);
    nex.resize(n1+1);
    for (int i = 1; i <= n; i++)
        if (ans[sortY[i].se] == 0)
            rem[equivalenceClass[sortY[i].se]].emplace_back(sortY[i].fi/last, sortY[i].se);
    for (int i = 1; i <= n1; i++) {
        int sz = rem[i].size();
        nex[i].resize(sz+1);
        iota(nex[i].begin(), nex[i].end(), 0);
    }
}




int main() {
//    freopen("chess.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].r;
    for (int i = 1; i <= n; i++) {
        a[i].x += 1'000'000'000;
        a[i].y += 1'000'000'000;
    }
    for (int i = 1; i <= n; i++) sortX[i] = {a[i].x, i};
    for (int i = 1; i <= n; i++) sortY[i] = {a[i].y, i};
    sort(sortX + 1, sortX + n + 1);
    sort(sortY + 1, sortY + n + 1);
    getNextCircleHelper::init();

    for (int i = 1; i <= n; i++) last = max(last, a[i].r);
    rebuild(last);


    int numberOfIterations = 0;


    while (1) {
//        assert(++numberOfIterations <= n+1);
        int cur = getNextCircle();
        if (cur == -1) break;
        if (last > a[cur].r * 2) rebuild(a[cur].r);

        int curX = a[cur].x/last, curY = a[cur].y/last;

        int stX = lower_bound(c + 1, c + n1 + 1, curX-2) - c;

        for (int i = stX; i <= n1 && c[i] <= curX+2; i++) {
            vector<ii> &curVector = rem[i];
            int stY = lower_bound(curVector.begin(), curVector.end(), ii{curY-2, 0}) - curVector.begin();
            for (int j = stY; j < curVector.size() && curVector[j].fi <= curY+2; j = getNext(i, j+1)) {
                if (ans[curVector[j].se] > 0) continue;
                del(curVector[j].se, cur);
                if (ans[curVector[j].se] == cur) nex[i][j] = j+1;
            }
        }
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
/*
3
29 1 37
93 14 22
74 66 30
*/

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13