Submission #111234

#	Time	Username	Problem	Language	Result	Execution time	Memory
111234		SamAnd	Circle selection (APIO18_circle_selection)	C++17	19 / 100	1960 ms	49896 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 300005;
struct ban
{
    int i;
    int x, y, r;
};
bool operator<(const ban& a, const ban& b)
{
    if (a.r < b.r)
        return true;
    if (a.r > b.r)
        return false;
    return a.i > b.i;
}

int n;
ban a[N];

int ans[N];

priority_queue<ban> q;
int get()
{
    while (1)
    {
        if (q.empty())
            return -1;
        ban t = q.top();
        q.pop();
        if (!ans[t.i])
            return t.i;
    }
}

bool stg(long long x1, long long y1, long long r1, long long x2, long long y2, long long r2)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2);
}

void solv0()
{
    for (int i = 1; i <= n; ++i)
        q.push(a[i]);
    while (1)
    {
        int i = get();
        if (i == -1)
            return;
        for (int j = 1; j <= n; ++j)
        {
            if (!ans[j])
            {
                if (stg(a[i].x, a[i].y, a[i].r, a[j].x, a[j].y, a[j].r))
                {
                    ans[j] = i;
                }
            }
        }
    }
}

void solv1()
{
    for (int i = 1; i <= n; ++i)
        q.push(a[i]);
    set<pair<int, int> > s;
    for (int i = 1; i <= n; ++i)
    {
        s.insert(m_p(a[i].x - a[i].r, i));
        s.insert(m_p(a[i].x + a[i].r, i));
    }
    while (1)
    {
        int i = get();
        if (i == -1)
            return;
        int l = a[i].x - a[i].r;
        int r = a[i].x + a[i].r;
        queue<int> q;
        for (set<pair<int, int> >::iterator it = s.lower_bound(m_p(l, 0)); it != s.end(); ++it)
        {
            if ((*it).first > r)
                break;
            ans[(*it).second] = i;
            q.push((*it).second);
        }
        while (!q.empty())
        {
            s.erase(m_p(a[q.front()].x - a[q.front()].r, q.front()));
            s.erase(m_p(a[q.front()].x + a[q.front()].r, q.front()));
            q.pop();
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        a[i].i = i;
        cin >> a[i].x >> a[i].y >> a[i].r;
    }
    if (n <= 5000)
        solv0();
    else
        solv1();
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13