Submission #97719

#	Time	Username	Problem	Language	Result	Execution time	Memory
97719		dalgerok	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1650 ms	91476 KiB

circle_selection

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;


const int N = 3e5 + 5;



int n, x[N], y[N], r[N], a[N];
int kill_[N], bound;

inline bool cmp(int xx, int yy){
    return r[xx] > r[yy] || (r[xx] == r[yy] && xx < yy);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(pair <int, int> x) const {
        static const uint64_t FIXED_RANDOM1 = chrono::steady_clock::now().time_since_epoch().count();
        static const uint64_t FIXED_RANDOM2 = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM1) ^ splitmix64(x.second + FIXED_RANDOM2);
    }
};
gp_hash_table < pair < int, int >, vector < int >, custom_hash > q;
inline void update(){
    q.clear();
    for(int i = 1; i <= n; i++){
        if(!kill_[i]){
            q[make_pair(x[i] / bound, y[i] / bound)].push_back(i);
        }
    }
}

inline bool intersect(int i, int j){
    return  1LL * (x[i] - x[j]) * (x[i] - x[j])
            +
            1LL * (y[i] - y[j]) * (y[i] - y[j])
            <=
            1LL * (r[i] + r[j]) * (r[i] + r[j]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
        a[i] = i;
    }
    sort(a + 1, a + n + 1, cmp);
    bound = 2e9 + 5;
    int pos = 1;
    while(true){
        while(pos <= n && kill_[a[pos]]){
            pos += 1;
        }
        if(pos == n + 1){
            break;
        }
        int cur = a[pos];
        if(2 * r[cur] <= bound){
            bound = r[cur];
            update();
        }
        kill_[cur] = cur;
        int xx = x[cur] / bound,
            yy = y[cur] / bound;
        for(int i = xx - 2; i <= xx + 2; i++){
            for(int j = yy - 2; j <= yy + 2; j++){
                if(q.find(make_pair(i, j)) != q.end()){
                    vector < int > nq;
                    for(auto it : q[make_pair(i, j)]){
                        if(intersect(cur, it)){
                            kill_[it] = cur;
                        }
                        else{
                            nq.push_back(it);
                        }
                    }
                    q[make_pair(i, j)] = nq;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << kill_[i] << " ";
    }
}
/**
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

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