제출 #260975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260975		emanIaicepsa	원 고르기 (APIO18_circle_selection)	C++14	7 / 100	3068 ms	19832 KiB

circle_selection

#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];

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;
}

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;
    }

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

    for(int i=1;i<=n;i++){
        if(del[arr[i].id]) continue;
        //dbg(arr[i].id);
        for(int j=1;j<=n;j++){
            if(del[arr[j].id]) continue;
            if(in(i,j)){
                del[arr[j].id] = arr[i].id;
            }
        }
        del[arr[i].id] = arr[i].id;
    }

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

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

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13