Submission #747777

#	Time	Username	Problem	Language	Result	Execution time	Memory
747777		1075508020060209tc	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3062 ms	18516 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define X first
#define Y second
int n;
pair<int,int>pts[300005];
int rr[300005];
int ans[300005];

int dis(int a,int b){
int ret=(pts[a].first-pts[b].first)*(pts[a].first-pts[b].first)+(pts[a].second-pts[b].second)*(pts[a].second-pts[b].second);
return ret;
}


signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>pts[i].X>>pts[i].Y>>rr[i];
    }

    while(1){
        int mx=0;
        for(int i=1;i<=n;i++){
            if(ans[i]){continue;}
            mx=max(mx,rr[i]);
        }
        if(mx==0){break;}
        int nw=0;
        for(int i=1;i<=n;i++){
            if(ans[i]){continue;}
            if(rr[i]==mx){
                nw=i;
                break;
            }
        }
        for(int i=1;i<=n;i++){
            if(ans[i]){continue;}
            if(dis(nw,i)<=(rr[i]+rr[nw])*(rr[i]+rr[nw])){
                ans[i]=nw;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }


}

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