oj.uz

Submission #864728

# Submission time Handle Problem Language Result Execution time Memory
864728 2023-10-23T13:54:17 Z danikoynov Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 339796 KB 
#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
*/

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 59740 KB Output is correct
2 Correct 11 ms 59892 KB Output is correct
3 Correct 11 ms 59740 KB Output is correct
4 Correct 11 ms 59740 KB Output is correct
5 Correct 11 ms 59740 KB Output is correct
6 Correct 11 ms 59740 KB Output is correct
7 Correct 11 ms 59740 KB Output is correct
8 Correct 11 ms 59740 KB Output is correct
9 Correct 11 ms 59740 KB Output is correct
10 Correct 11 ms 59740 KB Output is correct
11 Correct 11 ms 59740 KB Output is correct
12 Correct 11 ms 59740 KB Output is correct
13 Correct 11 ms 59740 KB Output is correct
14 Correct 11 ms 59740 KB Output is correct
15 Correct 11 ms 59740 KB Output is correct
16 Correct 12 ms 59992 KB Output is correct
17 Correct 12 ms 59740 KB Output is correct
18 Correct 12 ms 59880 KB Output is correct
19 Correct 16 ms 60248 KB Output is correct
20 Correct 16 ms 60096 KB Output is correct
21 Correct 16 ms 59996 KB Output is correct
22 Correct 117 ms 60092 KB Output is correct
23 Correct 119 ms 60080 KB Output is correct
24 Correct 117 ms 59992 KB Output is correct
25 Correct 119 ms 59996 KB Output is correct
26 Correct 116 ms 59992 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 113844 KB Output is correct
2 Correct 1179 ms 117496 KB Output is correct
3 Correct 1179 ms 117388 KB Output is correct
4 Correct 1181 ms 117680 KB Output is correct
5 Correct 1043 ms 116256 KB Output is correct
6 Correct 1018 ms 116400 KB Output is correct
7 Correct 1030 ms 116564 KB Output is correct
8 Correct 1008 ms 116564 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 59740 KB Output is correct
2 Execution timed out 3073 ms 64516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 339796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 59740 KB Output is correct
2 Correct 11 ms 59892 KB Output is correct
3 Correct 11 ms 59740 KB Output is correct
4 Correct 11 ms 59740 KB Output is correct
5 Correct 11 ms 59740 KB Output is correct
6 Correct 11 ms 59740 KB Output is correct
7 Correct 11 ms 59740 KB Output is correct
8 Correct 11 ms 59740 KB Output is correct
9 Correct 11 ms 59740 KB Output is correct
10 Correct 11 ms 59740 KB Output is correct
11 Correct 11 ms 59740 KB Output is correct
12 Correct 11 ms 59740 KB Output is correct
13 Correct 11 ms 59740 KB Output is correct
14 Correct 11 ms 59740 KB Output is correct
15 Correct 11 ms 59740 KB Output is correct
16 Correct 12 ms 59992 KB Output is correct
17 Correct 12 ms 59740 KB Output is correct
18 Correct 12 ms 59880 KB Output is correct
19 Correct 16 ms 60248 KB Output is correct
20 Correct 16 ms 60096 KB Output is correct
21 Correct 16 ms 59996 KB Output is correct
22 Correct 117 ms 60092 KB Output is correct
23 Correct 119 ms 60080 KB Output is correct
24 Correct 117 ms 59992 KB Output is correct
25 Correct 119 ms 59996 KB Output is correct
26 Correct 116 ms 59992 KB Output is correct
27 Correct 24 ms 60192 KB Output is correct
28 Correct 20 ms 59952 KB Output is correct
29 Correct 20 ms 60196 KB Output is correct
30 Correct 540 ms 59980 KB Output is correct
31 Correct 537 ms 59992 KB Output is correct
32 Correct 540 ms 59968 KB Output is correct
33 Correct 107 ms 63256 KB Output is correct
34 Correct 107 ms 63060 KB Output is correct
35 Correct 107 ms 63060 KB Output is correct
36 Execution timed out 3047 ms 62548 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 59740 KB Output is correct
2 Correct 11 ms 59892 KB Output is correct
3 Correct 11 ms 59740 KB Output is correct
4 Correct 11 ms 59740 KB Output is correct
5 Correct 11 ms 59740 KB Output is correct
6 Correct 11 ms 59740 KB Output is correct
7 Correct 11 ms 59740 KB Output is correct
8 Correct 11 ms 59740 KB Output is correct
9 Correct 11 ms 59740 KB Output is correct
10 Correct 11 ms 59740 KB Output is correct
11 Correct 11 ms 59740 KB Output is correct
12 Correct 11 ms 59740 KB Output is correct
13 Correct 11 ms 59740 KB Output is correct
14 Correct 11 ms 59740 KB Output is correct
15 Correct 11 ms 59740 KB Output is correct
16 Correct 12 ms 59992 KB Output is correct
17 Correct 12 ms 59740 KB Output is correct
18 Correct 12 ms 59880 KB Output is correct
19 Correct 16 ms 60248 KB Output is correct
20 Correct 16 ms 60096 KB Output is correct
21 Correct 16 ms 59996 KB Output is correct
22 Correct 117 ms 60092 KB Output is correct
23 Correct 119 ms 60080 KB Output is correct
24 Correct 117 ms 59992 KB Output is correct
25 Correct 119 ms 59996 KB Output is correct
26 Correct 116 ms 59992 KB Output is correct
27 Correct 1197 ms 113844 KB Output is correct
28 Correct 1179 ms 117496 KB Output is correct
29 Correct 1179 ms 117388 KB Output is correct
30 Correct 1181 ms 117680 KB Output is correct
31 Correct 1043 ms 116256 KB Output is correct
32 Correct 1018 ms 116400 KB Output is correct
33 Correct 1030 ms 116564 KB Output is correct
34 Correct 1008 ms 116564 KB Output is correct
35 Correct 11 ms 59740 KB Output is correct
36 Execution timed out 3073 ms 64516 KB Time limit exceeded
37 Halted 0 ms 0 KB -