Submission #864639

#	Time	Username	Problem	Language	Result	Execution time	Memory
864639		danikoynov	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3095 ms	58308 KiB

circle_selection

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

struct point
{
    ll x, y;
};

struct circle
{
    point centre;
    ll radius;
};

const int maxn = 3e5 + 10;

int n;
circle c[maxn];

void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> c[i].centre.x >> c[i].centre.y >> c[i].radius;
}

int used[maxn], par[maxn];

int find_biggest()
{
    int idx = -1;
    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;
        if (idx == -1 || c[i].radius > c[idx].radius)
            idx = i;
    }

    return idx;
}

ll distance(point A, point B)
{
    ll dx = (A.x - B.x);
    ll dy = (A.y - B.y);

    return dx * dx + dy * dy;
}
void simulate()
{
    while(true)
    {
        int idx = find_biggest();
        if (idx == -1)
            break;
        ///cout << "current " << idx << endl;
        for (int i = 1; i <= n; i ++)
        {
            if (used[i] == 1)
                continue;
            
            if (distance(c[idx].centre, c[i].centre) <=
                 (c[idx].radius + c[i].radius) * (c[idx].radius + c[i].radius))
                used[i] = 1, par[i] = idx;
        }
        
    }
}


void print()
{
    for (int i = 1; i <= n; i ++)
        cout << par[i] << " ";
    cout << endl;
}


void solve_subtask_2()
{
    set < pair < int, int > > lf, rf;
    set < pair < int, int > > act;

    for (int i = 1; i <= n; i ++)
    {
        lf.insert(make_pair(c[i].centre.x - c[i].radius, i));
        rf.insert(make_pair(c[i].centre.x + c[i].radius, i));
        act.insert(make_pair(c[i].radius, i));
    }
    
    while(!act.empty())
    {
        int idx = act.begin() -> second;
        int left = c[idx].centre.x - c[idx].radius;
        int right = c[idx].centre.x + c[idx].radius;

        while(true)
        {
            set < pair < int, int > > :: iterator it = lf.lower_bound({left, -1});
            if (it -> first <= right)
            {
                int i = it -> second;
                par[i] = idx;
                lf.erase(make_pair(c[i].centre.x - c[i].radius, i));
                rf.erase(make_pair(c[i].centre.x + c[i].radius, i));
                act.erase(make_pair(c[i].radius, i));
            }
            else
            {
                break;
            }
        }


        while(true)
        {
            set < pair < int, int > > :: iterator it = rf.lower_bound({left, -1});
            if (it -> first <= right)
            {
                int i = it -> second;
                par[i] = idx;
                lf.erase(make_pair(c[i].centre.x - c[i].radius, i));
                rf.erase(make_pair(c[i].centre.x + c[i].radius, i));
                act.erase(make_pair(c[i].radius, i));
            }
            else
            {
                break;
            }
        }
    }

}
void solve()
{
    input();
    bool all_on_x = true;
    for (int i = 1; i <= n; i ++)
    {
        if (c[i].centre.y != 0)
            all_on_x = false;
    }
    if (all_on_x)
        solve_subtask_2();
    else
        simulate();
    print();
}
int main()
{
    solve();
    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