oj.uz

Submission #864725

# Submission time Handle Problem Language Result Execution time Memory
864725 2023-10-23T13:52:28 Z danikoynov Circle selection (APIO18_circle_selection) C++14
19 / 100
 3000 ms 344436 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 59740 KB Output is correct
3 Correct 11 ms 59740 KB Output is correct
4 Correct 11 ms 59740 KB Output is correct
5 Correct 13 ms 59844 KB Output is correct
6 Correct 11 ms 59740 KB Output is correct
7 Correct 11 ms 59736 KB Output is correct
8 Correct 12 ms 59948 KB Output is correct
9 Correct 11 ms 59740 KB Output is correct
10 Correct 11 ms 59948 KB Output is correct
11 Correct 11 ms 59832 KB Output is correct
12 Correct 11 ms 59736 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 59872 KB Output is correct
16 Correct 12 ms 60232 KB Output is correct
17 Correct 12 ms 59996 KB Output is correct
18 Correct 12 ms 59996 KB Output is correct
19 Correct 15 ms 59996 KB Output is correct
20 Correct 16 ms 60136 KB Output is correct
21 Correct 16 ms 59996 KB Output is correct
22 Correct 117 ms 59992 KB Output is correct
23 Correct 118 ms 60084 KB Output is correct
24 Correct 116 ms 60088 KB Output is correct
25 Correct 118 ms 60096 KB Output is correct
26 Correct 116 ms 60088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 117604 KB Output is correct
2 Correct 1115 ms 117448 KB Output is correct
3 Correct 1150 ms 117164 KB Output is correct
4 Correct 1086 ms 117568 KB Output is correct
5 Correct 952 ms 116232 KB Output is correct
6 Correct 953 ms 116256 KB Output is correct
7 Correct 994 ms 116316 KB Output is correct
8 Correct 975 ms 116304 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 59736 KB Output is correct
2 Execution timed out 3050 ms 64456 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 3060 ms 344436 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 59740 KB Output is correct
3 Correct 11 ms 59740 KB Output is correct
4 Correct 11 ms 59740 KB Output is correct
5 Correct 13 ms 59844 KB Output is correct
6 Correct 11 ms 59740 KB Output is correct
7 Correct 11 ms 59736 KB Output is correct
8 Correct 12 ms 59948 KB Output is correct
9 Correct 11 ms 59740 KB Output is correct
10 Correct 11 ms 59948 KB Output is correct
11 Correct 11 ms 59832 KB Output is correct
12 Correct 11 ms 59736 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 59872 KB Output is correct
16 Correct 12 ms 60232 KB Output is correct
17 Correct 12 ms 59996 KB Output is correct
18 Correct 12 ms 59996 KB Output is correct
19 Correct 15 ms 59996 KB Output is correct
20 Correct 16 ms 60136 KB Output is correct
21 Correct 16 ms 59996 KB Output is correct
22 Correct 117 ms 59992 KB Output is correct
23 Correct 118 ms 60084 KB Output is correct
24 Correct 116 ms 60088 KB Output is correct
25 Correct 118 ms 60096 KB Output is correct
26 Correct 116 ms 60088 KB Output is correct
27 Correct 21 ms 60252 KB Output is correct
28 Correct 21 ms 60252 KB Output is correct
29 Correct 20 ms 60252 KB Output is correct
30 Correct 539 ms 60440 KB Output is correct
31 Correct 557 ms 60248 KB Output is correct
32 Correct 542 ms 60496 KB Output is correct
33 Correct 104 ms 65872 KB Output is correct
34 Correct 104 ms 66036 KB Output is correct
35 Correct 118 ms 65952 KB Output is correct
36 Execution timed out 3056 ms 64960 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 59740 KB Output is correct
3 Correct 11 ms 59740 KB Output is correct
4 Correct 11 ms 59740 KB Output is correct
5 Correct 13 ms 59844 KB Output is correct
6 Correct 11 ms 59740 KB Output is correct
7 Correct 11 ms 59736 KB Output is correct
8 Correct 12 ms 59948 KB Output is correct
9 Correct 11 ms 59740 KB Output is correct
10 Correct 11 ms 59948 KB Output is correct
11 Correct 11 ms 59832 KB Output is correct
12 Correct 11 ms 59736 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 59872 KB Output is correct
16 Correct 12 ms 60232 KB Output is correct
17 Correct 12 ms 59996 KB Output is correct
18 Correct 12 ms 59996 KB Output is correct
19 Correct 15 ms 59996 KB Output is correct
20 Correct 16 ms 60136 KB Output is correct
21 Correct 16 ms 59996 KB Output is correct
22 Correct 117 ms 59992 KB Output is correct
23 Correct 118 ms 60084 KB Output is correct
24 Correct 116 ms 60088 KB Output is correct
25 Correct 118 ms 60096 KB Output is correct
26 Correct 116 ms 60088 KB Output is correct
27 Correct 1164 ms 117604 KB Output is correct
28 Correct 1115 ms 117448 KB Output is correct
29 Correct 1150 ms 117164 KB Output is correct
30 Correct 1086 ms 117568 KB Output is correct
31 Correct 952 ms 116232 KB Output is correct
32 Correct 953 ms 116256 KB Output is correct
33 Correct 994 ms 116316 KB Output is correct
34 Correct 975 ms 116304 KB Output is correct
35 Correct 11 ms 59736 KB Output is correct
36 Execution timed out 3050 ms 64456 KB Time limit exceeded
37 Halted 0 ms 0 KB -