제출 #364638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364638		doowey	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	2860 ms	42192 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
ll cut = (1ll << 31);
int sol[N];
ll xi[N];
ll yi[N];
ll ri[N];

ll sq(ll v){
    return v * 1ll * v;
}

bool check(int i, int j){
    // sqrt((xi-xj)^2+(yi-yj)^2) <= (ri + rj)
    ll val = sq(xi[i] - xi[j]) + sq(yi[i] - yi[j]);
    ll cmp = sq(ri[i] + ri[j]);
    if(val <= cmp)
        return true;
    return false;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<pii> cir;
    for(int i = 1; i <= n; i ++ ){
        cin >> xi[i] >> yi[i] >> ri[i];
        cir.push_back({ri[i], -i});
    }
    sort(cir.begin(), cir.end());
    int id;
    bool has;
    ll ci, cj;
    int gg;
    set<pair<pii,int>> cv;
    for(int i = cir.size() - 1; i >= 0 ;i -- ){
        id = -cir[i].se;
        if(sol[id] == 0){
            has=false;
            while(cut/2ll >= ri[id]){
                has=true;
                cut /= 2ll;
            }

            if(has){
                cv.clear();
                for(int i = 1; i <= n; i ++ ){
                    if(sol[i] == 0){
                        cv.insert(mp(mp(xi[i]/cut,yi[i]/cut),i));
                    }
                }
            }
            ci = xi[id]/cut;
            cj = yi[id]/cut;
            for(ll p = -2; p <= 2; p ++ ){
                auto it = cv.lower_bound({mp(ci-p,cj-2),-1});
                while(it != cv.end()){
                    if((it->fi).fi != ci - p) break;
                    if((it->fi).se > cj + 2) break;
                    gg = it->se;
                    if(check(gg, id)){
                        sol[gg] = id;
                        it=cv.erase(it);
                    }
                    else{
                        it++;
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << sol[i] << " ";
    }
    cout << "\n";
    return 0;
}

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