Submission #405648

#	Time	Username	Problem	Language	Result	Execution time	Memory
405648		rqi	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1947 ms	383952 KiB

circle_selection

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef double db;

#define f first
#define s second
#define pb push_back
#define mp make_pair

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

mt19937 rng(127);
const int SZ = 100;

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


const uint64_t C = ll(2e18*3.1415926535)+71; // large odd number
const int RANDOM = rng(); // random 32-bit number
ll hashNum(ll x) {
    // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
    return __builtin_bswap64((x^RANDOM)*C);
}

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

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

bool circIntersect(int a, int b){
    ll dist_sq = (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
    if(dist_sq <= (r[a]+r[b])*(r[a]+r[b])){
        return true;
    }
    return false;
}

vector<pair<ll, int>> buckets[35];
int ans[mx];
gp_hash_table<pl, vi, hashFunc> g;
ll GRID;

ll fdiv(ll a, ll b){
    assert(b >= 1);
    if(a >= 0) return a/b;
    return (a+1)/b-1;
}

pl gridReduce(pl a){
    return mp(fdiv(a.f, GRID), fdiv(a.s, GRID));
}

void remDup(vpl& a){
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

vpl getCorners(int circ){
    vpl corners = vpl{mp(x[circ]+r[circ], y[circ]+r[circ]), mp(x[circ]-r[circ], y[circ]+r[circ]), mp(x[circ]-r[circ], y[circ]-r[circ]), mp(x[circ]+r[circ], y[circ]-r[circ])};
    vector<pl> res;
    for(auto u: corners){
        res.pb(gridReduce(u));
    }
    remDup(res);
    return res;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    // n = 300000;
    // clock_t c = clock();
    // cout << fixed << setprecision(6);
    
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
        // x[i] = rng() % SZ - SZ/2;
        // y[i] = rng() % SZ - SZ/2;
        // r[i] = 1 + rng() % SZ;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 35; j++){
            if(r[i] < (1LL<<j)){
                buckets[j-1].pb(mp(-r[i], i));
                break;
            }
        }
    }
    assert(sz(buckets[30]) == 0);
    //cout << db(clock()-c)/db(CLOCKS_PER_SEC) << "\n";

    int num = 0;
    for(int k = 29; k >= 0; k--){
        sort(all(buckets[k]));
        if(sz(buckets[k]) == 0) continue;
        g.clear();
        GRID = (1LL<<(k+2));
        for(int i = 1; i <= n; i++){
            if(ans[i] == 0){
                for(auto u: getCorners(i)){
                    g[u].pb(i);
                    num++;
                }
            }
        }

        for(auto circ: buckets[k]){
            int ind = circ.s;
            if(ans[ind] == 0){
                for(auto u: getCorners(ind)){
                    vi new_cands;
                    for(auto cand: g[u]){
                        //num++;
                        if(ans[cand] != 0) continue;
                        if(circIntersect(ind, cand)){
                            ans[cand] = ind;
                        }
                        else{
                            new_cands.pb(cand);
                        }
                    }
                    g[u] = new_cands;
                }
                assert(ans[ind] == ind);
            }
        }
    }
    // cout << num << "\n";
    //  cout << db(clock()-c)/db(CLOCKS_PER_SEC) << "\n";
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << "\n";
    // cout << db(clock()-c)/db(CLOCKS_PER_SEC) << "\n";
}

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