oj.uz

Submission #1095604

# Submission time Handle Problem Language Result Execution time Memory
1095604 2024-10-02T16:33:35 Z ConquerConquerer Circle selection (APIO18_circle_selection) C++14
23 / 100
 1167 ms 54816 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);
 
    sub4();
 
    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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 251 ms 24436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 54816 KB Output is correct
2 Correct 862 ms 53940 KB Output is correct
3 Correct 449 ms 33820 KB Output is correct
4 Correct 898 ms 54420 KB Output is correct
5 Correct 937 ms 54672 KB Output is correct
6 Correct 346 ms 27924 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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -