Submission #103656

#	Time	Username	Problem	Language	Result	Execution time	Memory
103656		osaaateiasavtnl	Circle selection (APIO18_circle_selection)	C++14	72 / 100	3040 ms	46688 KiB

circle_selection

#include<bits/stdc++.h>
using namespace std;
#define Point pair <int, int>
#define x first
#define y second
const int N = 3e5 + 7;
int n;
Point a[N];
int r[N];
int par[N];
int cur = 1 << 30;
vector<vector<int>> av;
vector<int> px;
int per[N];
bool compx(int i, int j) {
    return a[i].x < a[j].x;
}   
bool compy(int i, int j) {
    return a[i].y < a[j].y;
}   
bool used[N];
struct Comp {
    bool operator () (const int i, const int j) {
        return (r[i] > r[j]) || (r[i] == r[j] && i < j);
    }   
};
set <int,Comp> ms;
void build() {
    av.clear(); px.clear();
    int ptr = 0;
    while (ptr < n) {
        int r = ptr;
        while (r + 1 < n && a[per[ptr]].x / cur == a[per[r + 1]].x / cur) ++r;
        av.push_back({});
        for (int i = ptr; i <= r; ++i) {
            av.back().push_back(per[i]);
        }
        sort(av.back().begin(), av.back().end(), compy);
        px.push_back(a[per[ptr]].x / cur);
        ptr = r + 1;
    }   
}   
bool intersect(int i, int j) {
    typedef long long ll;
    return (ll)(a[i].x - a[j].x) * (a[i].x - a[j].x) + (ll)(a[i].y - a[j].y) * (a[i].y - a[j].y) <= (ll)(r[i] + r[j]) * (r[i] + r[j]);
}   
void check(int el, int i) {
    #ifdef HOME
    cout << "check " << el + 1 << ' ' << i + 1 << '\n';
    #endif
    if (used[i]) return;
    if (intersect(el, i)) {
        used[i] = 1;
        par[i] = el;
        ms.erase(i);
    }   
}   
void work(int el, int x, int y) {
    auto t = lower_bound(px.begin(), px.end(), x);
    if (*t == x) {
        int pos = t - px.begin();
        #ifdef HOME
        cout << "work " << el + 1 << ' ' << pos << '\n';
        #endif
        int l = -1, r = av[pos].size();
        while (l < r - 1) {
            int m = (l + r) >> 1;
            int i = av[pos][m];
            if (a[i].y / cur < y) l = m;
            else r = m;
        }   
        for (int i = r; i < (int)av[pos].size(); ++i) {
            if (a[av[pos][i]].y / cur != y) {
                break;
            }   
            check(el, av[pos][i]);
        }
    }   
}
void print_struct() {
    for (int i = 0; i < (int)av.size(); ++i) {
        cout << px[i] << " : ";
        for (int t : av[i]) cout << t + 1 << ' ';
        cout << '\n';
    }   
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].x >> a[i].y >> r[i];
    }   
    for (int i = 0; i < n; ++i) {
        per[i] = i;
    }   
    sort(per, per + n, compx);
    for (int i = 0; i < n; ++i) {
        ms.insert(i);
    }   
    build();
    while (ms.size()) {
        int i = *ms.begin();
        while ((cur >> 1) >= r[i]) {
            cur >>= 1;
            build();
        }
        #ifdef HOME
        cout << "eliminate " << i + 1 << '\n';
        cout << "cur " << cur << '\n';
        print_struct();
        #endif
        int ix = a[i].x / cur, iy = a[i].y / cur;
        for (int dx = -2; dx <= 2; ++dx) {
            for (int dy = -2; dy <= 2; ++dy) {
                work(i, ix + dx, iy + dy);
            }   
        }   
    }   
    for (int i = 0; i < n; ++i) {
        cout << par[i] + 1 << ' ';
    }   
    cout << '\n';
}   

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