oj.uz

Submission #1073870

# Submission time Handle Problem Language Result Execution time Memory
1073870 2024-08-25T01:01:44 Z ngrace Circle selection (APIO18_circle_selection) C++14
50 / 100
 1131 ms 62484 KB 
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

struct Circle{
    ll x, y, r, i;
};

int N;
v<Circle> C;

bool compC(Circle& a, Circle& b){
    if(a.r==b.r) return a.i<b.i;
    return a.r>b.r;
}
bool isect(Circle& a, Circle& b){
    ll dx=a.x-b.x;
    ll dy=a.y-b.y;
    ll r=a.r+b.r;
    return dx*dx+dy*dy <= r*r;
}

v<ll> eBy;

void sub1(){
    for(int i=0; i<N; i++){
        if(eBy[C[i].i]!=-1) continue;
        eBy[C[i].i] = C[i].i;
        for(int j=i+1; j<N; j++){
            if(eBy[C[j].i]==-1 && isect(C[i], C[j])){
                eBy[C[j].i] = C[i].i;
            }
        }
    }
}

void sub2(){
    set<ii> pts;
    for(int i=0; i<N; i++){
        pts.insert(make_pair(C[i].x-C[i].r, i));
        pts.insert(make_pair(C[i].x+C[i].r, i));
    }

    for(int i=0; i<N; i++){
        if(eBy[C[i].i]!=-1) continue;
        v<int> del;
        auto it = pts.lower_bound(make_pair(C[i].x-C[i].r, -1));
        while(it!=pts.end() && (*it).fi<=C[i].x+C[i].r){
            del.push_back((*it).se);
            it++;
        }
        for(int ind:del){
            eBy[C[ind].i] = C[i].i;
            pts.erase(make_pair(C[ind].x-C[ind].r, ind));
            pts.erase(make_pair(C[ind].x+C[ind].r, ind));
        }
    }
}

void sub3(){
    set<ii> xs;
    set<ii> ys;
    for(int i=0; i<N; i++){
        ys.insert({C[i].y-C[i].r, i});
        ys.insert({C[i].y+C[i].r, i});
        eBy[i] = i;
    }
    for(ii y:ys){
        ll x = C[y.se].x;

        if(C[y.se].y+C[y.se].r==y.fi) xs.erase({x,y.se});

        auto it = xs.lower_bound({x,-1});
        if(it!=xs.end()){
            ll ind = (*it).se;
            if(isect(C[y.se], C[ind])){
                ll e = (compC(C[y.se], C[ind]) ? y.se : ind);
                eBy[C[y.se].i] = C[e].i;
                eBy[C[ind].i] = C[e].i;
            }
        }
        if(it!=xs.begin()){
            it--;
            ll ind = (*it).se;
            if(isect(C[y.se], C[ind])){
                ll e = (compC(C[y.se], C[ind]) ? y.se : ind);
                eBy[C[y.se].i] = C[e].i;
                eBy[C[ind].i] = C[e].i;
            }
        }

        if(C[y.se].y-C[y.se].r == y.fi) xs.insert({x,y.se});
    }
}

void sub4(){
    map<ii, v<ll>> grid;
    for(int i=0; i<N; i++){
        C[i].x+=1e9;
        C[i].y+=1e9;
        grid[{C[i].x/C[i].r, C[i].y/C[i].r}].push_back(i);
    }
    for(int i=0; i<N; i++){
        Circle& cur = C[i];
        if(eBy[cur.i]!=-1) continue;
        for(ll x=cur.x/cur.r - 2; x<=cur.x/cur.r+2; x++){
            for(ll y=cur.y/cur.r-2; y<=cur.y/cur.r+2; y++){
                if(grid.find({x,y})==grid.end()) continue;
                for(ll c:grid[{x,y}]){
                    if(eBy[C[c].i]==-1 && isect(C[c],cur)) eBy[C[c].i] = cur.i;
                }
            }
        }
    }
}

void full(){

}

int main(){
    cin>>N;
    bool s2 = true;
    bool s4 = true;
    for(int i=0; i<N; i++){
        ll x,y,r;
        cin>>x>>y>>r;
        C.push_back({x,y,r,i});
        s2 = s2 && y==0;
        s4 = s4 && r==C[0].r;
    }
    sort(C.begin(), C.end(), compC);

    eBy = v<ll>(N,-1);

    if(N<=5000 && false) sub1();
    else if(s2) sub2();
    else if(s4) sub4();
    else sub3();

    for(int i:eBy) cout<<i+1<<" ";
    cout<<endl;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 61264 KB Output is correct
2 Correct 758 ms 61100 KB Output is correct
3 Correct 798 ms 62368 KB Output is correct
4 Correct 755 ms 62484 KB Output is correct
5 Correct 608 ms 57376 KB Output is correct
6 Correct 618 ms 56020 KB Output is correct
7 Correct 615 ms 57504 KB Output is correct
8 Correct 597 ms 56988 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 167 ms 20180 KB Output is correct
3 Correct 666 ms 58268 KB Output is correct
4 Correct 641 ms 58788 KB Output is correct
5 Correct 684 ms 58280 KB Output is correct
6 Correct 306 ms 31920 KB Output is correct
7 Correct 141 ms 16336 KB Output is correct
8 Correct 27 ms 3788 KB Output is correct
9 Correct 723 ms 59300 KB Output is correct
10 Correct 738 ms 58528 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1131 ms 53404 KB Output is correct
2 Correct 944 ms 53920 KB Output is correct
3 Correct 483 ms 32672 KB Output is correct
4 Correct 959 ms 55944 KB Output is correct
5 Correct 946 ms 56220 KB Output is correct
6 Correct 351 ms 29340 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -