Submission #932195

#	Time	Username	Problem	Language	Result	Execution time	Memory
932195		beepbeepsheep	Circle selection (APIO18_circle_selection)	C++17	7 / 100	25 ms	1368 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#define iiii tuple<ll,ll,ll,ll>

const ll maxn=5005;

iii arr[maxn];
ll ans[maxn];
iiii ord[maxn];
bool cmp(iiii a, iiii b){
    if (get<2>(a)==get<2>(b)) return get<3>(a)< get<3>(b);
    return get<2>(a)>get<2>(b);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,a,b,c;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a>>b>>c;
        arr[i]={a,b,c};
        ord[i]={a,b,c,i};
    }
    sort(ord+1,ord+n+1,cmp);
    ll x1,x2,y1,y2,r1,r2,idx1,idx2;
    for (int i=1;i<=n;i++){
        tie(x1,y1,r1,idx1)=ord[i];
        for (int j=1;j<=n;j++){
            
            tie(x2,y2,r2,idx2)=ord[j];
            if (idx1!=idx2 && ans[idx2]!=idx2) continue;
            //cerr<<i<<' '<<idx<<' '<<(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<<' '<<(r1+r2)*(r1+r2)<<endl;
            if ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=(r1+r2)*(r1+r2)){
                ans[idx1]=idx2;
                break;
            }
        }
    }
    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