제출 #864728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864728		danikoynov	원 고르기 (APIO18_circle_selection)	C++14	19 / 100	3074 ms	339796 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;
    int idx;
};

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;
        c[i].idx = i;
    }
}

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));
    }
    
    int last = n + 1;
    while(!act.empty())
    {
        int idx = -act.rbegin() -> 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 == lf.end())
                break;

            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.upper_bound({right, -1});
            if (it == rf.begin())
                break;
            it = prev(it);
            if (it -> first >= left)
            {
                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;
            }
        }

    }

}

bool cmp_x(circle  c1, circle c2)
{
    if (c1.centre.x != c2.centre.x)
        return (c1.centre.x < c2.centre.x);
    return (c1.centre.y < c2.centre.y);
}

bool cmp_y(circle  c1, circle c2)
{
    if (c1.centre.y != c2.centre.y)
        return (c1.centre.y < c2.centre.y);
    return (c1.centre.x < c2.centre.x);
}

set < pair < int, int > > tree[4 * maxn];
int rev[maxn];

void divide(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].insert({c[left].centre.y, left});
        return;
    }

    int mid = (left + right) / 2;
    divide(root * 2, left, mid);
    divide(root * 2 + 1, mid + 1, right);

    for (pair < int, int > cur : tree[root * 2])
        tree[root].insert(cur);

    for (pair < int, int > cur : tree[root * 2 + 1])
        tree[root].insert(cur);
}

void remove(int root, int left, int right, int pos)
{   
    tree[root].erase({c[pos].centre.y, pos});
    if (left == right)
        return;

    int mid = (left + right) / 2;
    if (pos <= mid)
        remove(root * 2, left, mid, pos);
    else
        remove(root * 2 + 1, mid + 1, right, pos);

    return;
}

vector < int > to_rem;
void check(int root, int left, int right, int qleft, int qright, circle cur)
{
    ///cout << "check " << root << " " << left << " " << right << " " << qleft << " " << qright << endl;
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        set < pair < int, int > > :: iterator it = tree[root].lower_bound({cur.centre.y - 2 * cur.radius, -1});
        set < pair < int, int > > :: iterator to = tree[root].upper_bound({cur.centre.y + 2 * cur.radius, n + 1});
        while(it != to)
        {
            if (distance(cur.centre, c[it -> second].centre) <=
                4 * cur.radius * cur.radius)
                to_rem.push_back(it -> second);
            it ++;
        }
        return;
    }

    int mid = (left + right) / 2;
    check(root * 2, left, mid, qleft, qright, cur);
    check(root * 2 + 1, mid + 1, right, qleft, qright, cur);

}
void solve_subtask_4()
{
    
    sort(c + 1, c + n + 1, cmp_x);
    for (int i = 1; i <= n; i ++)
    {
        rev[c[i].idx] = i;

    }

    divide(1, 1, n);

    int pivot = 1, cnt = 0;
    while(true)
    {
        //cnt ++;
        //assert(cnt < 15);
        while(pivot <= n && used[pivot])
            pivot ++;
        ///cout << "pivot " << pivot << endl;
        if (pivot > n)
            break;

        to_rem.clear();

        circle cur = c[rev[pivot]];
        int left = cur.centre.x - 2 * cur.radius;
        int right = cur.centre.x + 2 * cur.radius;
        ///cout << "range " << left << " " << right << endl;
        int lf = 1, rf = n;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (c[mf].centre.x < left)
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        int lb = lf;

        lf = 1;
        rf = n;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (c[mf].centre.x <= right)
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        int rb = rf;
        
        check(1, 1, n, lb, rb, cur);

        /**cout << "check" << endl;
        
        cout << to_rem.size() << endl;
        for (int cur : to_rem)
            cout << c[cur].idx << " ";
            cout << endl;*/

        
        for (int cur : to_rem)
        {
            if (used[c[cur].idx] == 1)
                continue;
            remove(1, 1, n, cur);
            ///cout << "USED " << c[cur].idx << endl;
            used[c[cur].idx] = 1;
            par[c[cur].idx] = pivot;
        }
    }
}
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;
    }
    bool all_same_radius = true;
    for (int i = 2; i <= n; i ++)
    {
        if (c[i].radius != c[1].radius)
            all_same_radius = false;
    }
    if (all_same_radius)
        solve_subtask_4();
    else
    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

11
9 0 2
13 0 1
11 0 2
3 0 2
3 0 1
12 0 1
9 0 5
2 0 2
5 0 1
14 0 2
14 0 1

11
9 9 2
13 2 2
11 8 2
3 3 2
3 12 2
12 14 2
9 8 2
2 8 2
5 2 2
14 4 2
14 14 2

1 2 1 4 5 6 1 8 4 2 6
1 2 1 4 5 6 1 8 4 2 6
*/

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In function 'void solve_subtask_2()':
circle_selection.cpp:98:9: warning: unused variable 'last' [-Wunused-variable]
   98 |     int last = n + 1;
      |         ^~~~
circle_selection.cpp: In function 'void solve_subtask_4()':
circle_selection.cpp:239:20: warning: unused variable 'cnt' [-Wunused-variable]
  239 |     int pivot = 1, cnt = 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