Submission #1108449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108449		simona1230	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3068 ms	21320 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
struct circle
{
    long long x,y,r,i;
    circle(){}
    circle(long long _x,long long _y,long long _r,long long _i)
    {
        x=_x;
        y=_y;
        r=_r;
        i=_i;
    }
};

long long n;
circle a[200001];

bool cmp(circle c1,circle c2)
{
    if(c1.r==c2.r)return c1.i<c2.i;
    return c1.r>c2.r;
}

void read()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].r;
        a[i].i=i;
    }

    sort(a+1,a+n+1,cmp);
}

long long used[200001];

bool intersect(circle c1,circle c2)
{
    long long d1=(c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y);
    long long d2=(c1.r+c2.r)*(c1.r+c2.r);
    return d1<=d2;
}

void solve()
{
    for(long long i=1;i<=n;i++)
    {
        if(used[a[i].i])continue;

        for(long long j=i;j<=n;j++)
        {
            if(used[a[j].i])continue;
            if(intersect(a[i],a[j]))
                used[a[j].i]=a[i].i;
        }
    }

    for(long long i=1;i<=n;i++)
        cout<<used[i]<<" ";
    cout<<endl;
}

int main()
{
    read();
    solve();
    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