Submission #364614

#	Time	Username	Problem	Language	Result	Execution time	Memory
364614		doowey	원 고르기 (APIO18_circle_selection)	C++14	72 / 100	3083 ms	70392 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;
}

map<pii, int> idx;
set<int> V[N];
int cid;

void add(pii x){
    if(idx.count(x)) return;
    idx[x]=cid;
    cid++;
}

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;
    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){
                idx.clear();
                for(int i = 0 ; i < cid; i ++ ){
                    V[i].clear();
                }
                cid = 0;
                for(int i = 1; i <= n; i ++ ){
                    if(sol[i] == 0){
                        add(mp(xi[i]/cut, yi[i]/cut));
                        V[idx[mp(xi[i]/cut,yi[i]/cut)]].insert(i);
                    }
                }
            }
            ci = xi[id]/cut;
            cj = yi[id]/cut;
            for(ll p = -2; p <= 2; p ++ ){
                for(ll q = -2 ; q <= 2; q ++ ){
                    if(idx.count(mp(ci+p,cj+q))){
                        gg = idx[mp(ci + p, cj + q)];
                        vector<int> del;
                        for(auto x : V[gg]){
                            if(check(id, x)){
                                del.push_back(x);
                            }
                        }
                        for(auto q : del){
                            V[gg].erase(q);
                            sol[q]=id;
                        }
                    }
                }
            }
        }
    }
    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: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13