oj.uz

Submission #1095678

# Submission time Handle Problem Language Result Execution time Memory
1095678 2024-10-03T00:22:54 Z ConquerConquerer Circle selection (APIO18_circle_selection) C++14
23 / 100
 1188 ms 54720 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 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;
                }
            }
        }
    }
}
 
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 1 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 265 ms 24568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 1188 ms 54720 KB Output is correct
2 Correct 953 ms 53884 KB Output is correct
3 Correct 500 ms 33940 KB Output is correct
4 Correct 984 ms 54252 KB Output is correct
5 Correct 986 ms 54512 KB Output is correct
6 Correct 364 ms 27876 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 -