제출 #111230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111230		SamAnd	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	420 ms	13560 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;
                }
            }
        }
    }
}

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();
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
    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