oj.uz

Submission #260991

# Submission time Handle Problem Language Result Execution time Memory
260991 2020-08-11T09:18:16 Z emanIaicepsa Circle selection (APIO18_circle_selection) C++14
12 / 100
 831 ms 55288 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define vi vector<int>
#define pb emplace_back
#define fi first
#define se second
#define all(n) (n).begin(),(n).end()
#define mem(n,m) memset(n,m,sizeof(n))
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){cerr<<x<<'\n';}
template<typename A,typename ...B> void _do(A x,B ...y){cerr<<x<<", ";_do(y...);}

struct circle{
    ll x, y, r, id;
    bool operator<(const circle &b){
        if(r!=b.r) return r>b.r;
        return id<b.id;
    }
}arr[300005];

int n, del[300005], fr[300005], ba[300005];

bool in(ll i,ll j){
    ll R = arr[i].r + arr[j].r;
    ll dx = arr[i].x - arr[j].x, dy = arr[i].y - arr[j].y;
    return dx*dx + dy*dy <= R*R;
}

set<pii> s;

signed main(){
	IOS;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].y>>arr[i].r;
        arr[i].id = i;
        s.insert({arr[i].x - arr[i].r, i});
        s.insert({arr[i].x + arr[i].r, i});
    }

    sort(arr+1,arr+1+n);

    for(int i=1;i<=n;i++){
        if(del[arr[i].id]) continue;
        //dbg(arr[i].id);
        auto iter = s.lower_bound({arr[i].x-arr[i].r,-1});
        while(iter!=s.end() && iter->fi <= arr[i].x + arr[i].r ){
            //dbg(iter->fi, iter->se);
            if(!del[iter->se]) del[iter->se] = arr[i].id;
            iter = s.erase(iter);
        }
        del[arr[i].id] = arr[i].id;
    }

    for(int i=1;i<=n;i++) cout<<del[i]<<" \n"[i==n];

}
/*
11
9 0 2
13 0 1
11 0 2
3 0 2
3 0 1
12 0 1
9 0 5
2 0 2
5 0 1
14 0 2
14 0 1
*/

Subtask #1
0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 50680 KB Output is correct
2 Correct 831 ms 50552 KB Output is correct
3 Correct 824 ms 50296 KB Output is correct
4 Correct 820 ms 50680 KB Output is correct
5 Correct 697 ms 50424 KB Output is correct
6 Correct 707 ms 55160 KB Output is correct
7 Correct 735 ms 55288 KB Output is correct
8 Correct 685 ms 55164 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -