Submission #439978

#	Time	Username	Problem	Language	Result	Execution time	Memory
439978		DJeniUp	Circle selection (APIO18_circle_selection)	C++17	7 / 100	380 ms	17188 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define pb push_back
#define fr first
#define sc second

ll n;

struct D{
    ll x,y,r,N;
}d[300007];

bool mcp(D d1, D d2){
    if(d1.r!=d2.r)return d1.r>d2.r;
    return d1.N<d2.N;
}

void RES(){
    ll res[5007];
    sort(d+1,d+1+n,mcp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if((d[j].x-d[i].x)*(d[j].x-d[i].x)+(d[j].y-d[i].y)*(d[j].y-d[i].y)<=(d[j].r+d[i].r)*(d[j].r+d[i].r) && (res[d[j].N]==d[j].N || i==j)){
                res[d[i].N]=d[j].N;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
    return ;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i].x>>d[i].y>>d[i].r;
        d[i].N=i;
    }
    if(n<=5000){
        RES();
        return 0;
    }

    return 0;
}
/*

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