Submission #744414

#	Time	Username	Problem	Language	Result	Execution time	Memory
744414		Abito	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3040 ms	1048576 KiB

circle_selection

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ep insert
#define pow pwr
#define sqrt sqrtt
#define elif else if
#define y1 YONE
#define int long long
using namespace std;
struct circle{
    int x,y,r,idx;
};
bool cmp(circle x,circle y){
    if (x.r!=y.r) return x.r>y.r;
    return x.idx<y.idx;
}
int dis(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
const int N=1e6+5;
int n,ans[N];
circle a[N];
vector<int> adj[N];
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for (int i=1;i<=n;i++) {cin>>a[i].x>>a[i].y>>a[i].r;a[i].idx=i;}
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            int x=dis(a[i].x,a[i].y,a[j].x,a[j].y),y=(a[i].r+a[j].r)*(a[i].r+a[j].r);
            if (x>y) continue;
            adj[i].pb(j);
        }
    }
    for (int i=1;i<=n;i++){
        if (ans[a[i].idx]) continue;
        for (auto u:adj[i]){
            if (ans[a[u].idx]) continue;
            ans[a[u].idx]=a[i].idx;
        }
    }
    for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

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