Submission #119068

#	Time	Username	Problem	Language	Result	Execution time	Memory
119068		Charis02	Circle selection (APIO18_circle_selection)	C++14	7 / 100	724 ms	35980 KiB

circle_selection

#include<iostream>
#include<set>
#include<cmath>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1000004
#define INF 1e9+7

using namespace std;

struct circle{
    ll x;
    ll y;
    ll r;
    ll id;
};

bool by_r(const circle &a,const circle &b)
{
    if(a.r == b.r)
    {
        return a.id < b.id;
    }

    return a.r > b.r;
}

ll n;
circle ar[N];
pair < ll,ll > v[N];
bool used[N];
set < ll > rs,ys;
ll ans[N];

double dist(ll x1,ll y1,ll x2,ll y2)
{
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

bool intersect(const circle &a,const circle &b)
{
    double c1c2 = dist(a.x,a.y,b.x,b.y);

    return (c1c2 <= a.r + b.r);
}

void first_subtask()
{
    rep(i,1,n+1)
    {
        if(used[i])
            continue;
        else
        {
            ans[ar[i].id] = ar[i].id;
            used[i] = true;

            rep(j,i+1,n+1)
            {
                if(used[j])
                    continue;

                if(intersect(ar[i],ar[j]))
                {
                    ans[ar[j].id] = ar[i].id;
                    used[j] = true;
                }
            }
        }
    }

    return;
}

void second_subtask()
{
    rep(i,1,n+1)
    {
        v[i].first = ar[i].x - ar[i].r;
        v[i].second = ar[i].x + ar[i].r;
    }

    sort(v+1,v+n+1);
}

void third_subtask()
{

}

void fourth_subtask()
{

}

void solve()
{
    cin >> n;

    rep(i,1,n+1)
    {
        cin >> ar[i].x >> ar[i].y >> ar[i].r;

        ar[i].id = i;

        rs.insert(ar[i].r);
        ys.insert(ar[i].y);
    }

    sort(ar+1,ar+n+1,by_r);

    if(n <= 5000)
    {
        first_subtask();
    }
    if(ys.size() == 1)
    {
        second_subtask();
    }
    else if(rs.size() == 1)
    {
        fourth_subtask();
    }
    else
    {
        third_subtask();
    }

    rep(i,1,n+1)
    {
        cout << ans[i] << " ";
    }

    return;
}

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