제출 #364613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364613		doowey	원 고르기 (APIO18_circle_selection)	C++14	49 / 100	3117 ms	638268 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;
    map<pii, set<int>> idk;
    ll ci, cj;
    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){
                idk.clear();
                for(int j =  1; j <= n; j ++ ){
                    if(sol[j] == 0){
                        idk[mp(xi[j]/cut,yi[j]/cut)].insert(j);
                    }
                }
            }
            ci = xi[id]/cut;
            cj = yi[id]/cut;
            vector<int> del;
            for(ll p = -2; p <= 2; p ++ ){
                for(ll q = -2 ; q <= 2; q ++ ){
                    for(auto v : idk[mp(ci + p, cj + q)]){
                        if(check(id,v)){
                            del.push_back(v);
                        }
                    }
                }
            }
            for(auto x : del){
                sol[x]=id;
                idk[mp(xi[x]/cut,yi[x]/cut)].erase(x);
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << sol[i] << " ";
    }
    cout << "\n";
    return 0;
}

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