Submission #403846

#	Time	Username	Problem	Language	Result	Execution time	Memory
403846		rqi	Circle selection (APIO18_circle_selection)	C++14	19 / 100	865 ms	58992 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef vector<int> vi;

#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define mp make_pair
#define lb lower_bound
#define ins insert

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct hashFunc{
    size_t operator()(const pl& a)const {
        return a.f ^(a.s+1);
    }
};

const int mx = 300005;
int n;
ll x[mx];
ll y[mx];
ll r[mx];
bool present[mx];
int ans[mx];

bool circleIntersect(int a, int b){
    ll dist = (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
    if(dist <= (r[a]+r[b])*(r[a]+r[b])) return 1;
    return 0;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    //gp_hash_table<pl, vi, hashFunc> g;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
    }
    vector<pair<ll, int>> v;
    for(int i = 1; i <= n; i++){
        v.pb(mp(-r[i], i));
    }
    sort(all(v));
    vi inds;
    for(int i = 0; i < n; i++){
        inds.pb(v[i].s);
    }

    if(n <= 5000){
        for(int i = 1; i <= n; i++){
            present[i] = 1;
        }
        for(auto ind: inds){
            if(present[ind]){
                present[ind] = 0;
                ans[ind] = ind;
                for(int i = 1; i <= n; i++){
                    if(present[i] && circleIntersect(i, ind)){
                        present[i] = 0;
                        ans[i] = ind;
                    }
                }
            }
            
        }
        for(int i = 1; i <= n; i++){
            cout << ans[i] << " ";
        }
        cout << "\n";
        exit(0);
    }

    bool allYs = 1;
    for(int i = 1; i <= n; i++){
        if(y[i] != 0){
            allYs = 0;
        }
    }
    if(allYs){
        set<pair<ll, int>> lefts;
        set<pair<ll, int>> rights;
        for(auto ind: inds){
            lefts.ins(mp(x[ind]-r[ind], ind));
            rights.ins(mp(x[ind]+r[ind], ind));
        }

        for(int i = 1; i <= n; i++){
            present[i] = 1;
        }
        for(auto ind: inds){
            //cout << "ind: " << ind << "\n";
            if(!present[ind]) continue;
            present[ind] = 0;
            ans[ind] = ind;
            //cout << "LEFTS: " << "\n";
            while(true){
                auto it = lefts.lb(mp(x[ind]-r[ind], 0));
                if(it == lefts.end()) break;
                if(it->f > x[ind]+r[ind]) break;
                int circ_ind = it->s;
                //cout << "circ_ind: " << circ_ind << "\n";
                lefts.erase(it);
                if(!present[circ_ind]) continue;
                //cout << "present" << "\n";
                present[circ_ind] = 0;
                ans[circ_ind] = ind;
            }
            //cout << "RIGHTS: " << "\n";
            while(true){
                auto it = rights.lb(mp(x[ind]+r[ind]+1, 0));
                if(it == rights.begin()) break;
                it = prev(it);
                if(it->f < x[ind]-r[ind]) break;
                int circ_ind = it->s;
                //cout << "circ_ind: " << circ_ind << "\n";
                rights.erase(it);
                if(!present[circ_ind]) continue;
                //cout << "present" << "\n";
                present[circ_ind] = 0;
                ans[circ_ind] = ind;
            }
        }
        for(int i = 1; i <= n; i++){
            cout << ans[i] << " ";
        }
        cout << "\n";
        exit(0);
    }

    
}

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