oj.uz

Submission #866312

# Submission time Handle Problem Language Result Execution time Memory
866312 2023-10-25T20:59:40 Z danikoynov Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 59512 KB 
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
struct point
{
    ll x, y;
 
    point(ll _x = 0, ll _y = 0)
    {
        x = _x;
        y = _y;
    }
 
    void get()
    {
        cin >> x >> y;
    }
};
 
struct circle
{
    point centre;
    ll radius;
    int idx;
 
    circle(point _centre = point(), ll _radius = 0, int _idx = 0)
    {
        centre = _centre;
        radius = _radius;
        idx = _idx;
    }
 
    void get()
    {
        centre.get();
        cin >> radius;
    }
};

ll get_distance(point A, point B)
{
    return (A.x - B.x) * (A.x - B.x) +
            (A.y - B.y) * (A.y - B.y);
}

bool intersect(circle c1, circle c2)
{
    ll distance = get_distance(c1.centre, c2.centre);

    return (distance <= (c1.radius + c2.radius) * (c1.radius + c2.radius));
        
}
const int maxn = 3e5 + 10;
const int inf = 1e9 + 10;
 
bool cmpx(circle c1, circle c2)
{
    return c1.centre.x < c2.centre.x;
}
 
bool cmpy(circle c1, circle c2)
{
    return c1.centre.y < c2.centre.y;
}
 

int n;
circle c[maxn], cx[maxn], cy[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        c[i].get();
        c[i].idx = i;
        cx[i] = cy[i] = c[i];
    }
}

void sort_arrays()
{
    sort(cx + 1, cx + n + 1, cmpx);
    sort(cy + 1, cy + n + 1, cmpy);
}
 
 
vector < vector < circle > > field;
bool eliminated[maxn];
int parent[maxn];
point comp[maxn];

void restructure(int block)
{
    field.clear();
    vector < int > dx;
    int last = -inf;
    for (int i = 1; i <= n; i ++)
    {
        if (eliminated[cx[i].idx])
            continue;
        
        int cur = cx[i].centre.x / block;
        if (cur != last)
            field.emplace_back();
        
        comp[cx[i].idx].x = field.size() - 1;
    
        last = cur;
    }

    for (int i = 1; i <= n; i ++)
    {
        if (eliminated[cy[i].idx])
            continue;

        comp[cy[i].idx].y = field[comp[cy[i].idx].x].size();
        field[comp[cy[i].idx].x].push_back(cy[i]);
    }


}
 
 
void simulate()
{
    int last_block = 0;
    for (int i = 1; i <= n; i ++)
        last_block = max(last_block, (int)c[i].radius);

    restructure(last_block);

    while(true)
    {
        int idx = -1;
        for (int i = 1; i <= n; i ++)
        {
            if (eliminated[i])
                continue;
            if (idx == -1 || c[i].radius > c[idx].radius)
                idx = i;
        }

        if (idx == -1)
            break;  
        
        if (c[idx].radius <= last_block / 2)
        {
            last_block = c[idx].radius;
            restructure(last_block);
        }

        int cor_x = comp[idx].x, cor_y = comp[idx].y;
        for (int i = 0; i < field.size(); i ++)
        {
            for (int j = 0; j < field[i].size(); j ++)
            {
                if (eliminated[field[i][j].idx])
                    continue;
                if (intersect(field[i][j], c[idx]))
                {
                    parent[field[i][j].idx] = idx;
                    eliminated[field[i][j].idx] = 1;
                }
            }
        }

    }

    for (int i = 1; i <= n; i ++)
        cout << parent[i] << " ";
    cout << endl;
}
void solve()
{
    input();
    sort_arrays();
    simulate();
}
 
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

*/

Compilation message

circle_selection.cpp: In function 'void simulate()':
circle_selection.cpp:155:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<circle> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for (int i = 0; i < field.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~
circle_selection.cpp:157:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<circle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for (int j = 0; j < field[i].size(); j ++)
      |                             ~~^~~~~~~~~~~~~~~~~
circle_selection.cpp:154:13: warning: unused variable 'cor_x' [-Wunused-variable]
  154 |         int cor_x = comp[idx].x, cor_y = comp[idx].y;
      |             ^~~~~
circle_selection.cpp:154:34: warning: unused variable 'cor_y' [-Wunused-variable]
  154 |         int cor_x = comp[idx].x, cor_y = comp[idx].y;
      |                                  ^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34648 KB Output is correct
2 Correct 6 ms 34652 KB Output is correct
3 Correct 5 ms 34568 KB Output is correct
4 Correct 5 ms 34648 KB Output is correct
5 Correct 5 ms 34588 KB Output is correct
6 Correct 5 ms 34904 KB Output is correct
7 Correct 6 ms 34652 KB Output is correct
8 Correct 5 ms 34904 KB Output is correct
9 Correct 6 ms 34648 KB Output is correct
10 Correct 6 ms 34740 KB Output is correct
11 Correct 6 ms 34652 KB Output is correct
12 Correct 6 ms 34652 KB Output is correct
13 Correct 6 ms 34652 KB Output is correct
14 Correct 6 ms 34584 KB Output is correct
15 Correct 5 ms 34652 KB Output is correct
16 Correct 7 ms 34652 KB Output is correct
17 Correct 7 ms 34652 KB Output is correct
18 Correct 7 ms 34652 KB Output is correct
19 Correct 11 ms 35164 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35192 KB Output is correct
22 Correct 146 ms 35064 KB Output is correct
23 Correct 106 ms 35168 KB Output is correct
24 Correct 137 ms 35400 KB Output is correct
25 Correct 119 ms 35164 KB Output is correct
26 Correct 138 ms 35164 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 52180 KB Output is correct
2 Correct 297 ms 51248 KB Output is correct
3 Correct 361 ms 54796 KB Output is correct
4 Correct 301 ms 59512 KB Output is correct
5 Execution timed out 3009 ms 54032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34652 KB Output is correct
2 Execution timed out 3068 ms 40080 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 3029 ms 51508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34648 KB Output is correct
2 Correct 6 ms 34652 KB Output is correct
3 Correct 5 ms 34568 KB Output is correct
4 Correct 5 ms 34648 KB Output is correct
5 Correct 5 ms 34588 KB Output is correct
6 Correct 5 ms 34904 KB Output is correct
7 Correct 6 ms 34652 KB Output is correct
8 Correct 5 ms 34904 KB Output is correct
9 Correct 6 ms 34648 KB Output is correct
10 Correct 6 ms 34740 KB Output is correct
11 Correct 6 ms 34652 KB Output is correct
12 Correct 6 ms 34652 KB Output is correct
13 Correct 6 ms 34652 KB Output is correct
14 Correct 6 ms 34584 KB Output is correct
15 Correct 5 ms 34652 KB Output is correct
16 Correct 7 ms 34652 KB Output is correct
17 Correct 7 ms 34652 KB Output is correct
18 Correct 7 ms 34652 KB Output is correct
19 Correct 11 ms 35164 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35192 KB Output is correct
22 Correct 146 ms 35064 KB Output is correct
23 Correct 106 ms 35168 KB Output is correct
24 Correct 137 ms 35400 KB Output is correct
25 Correct 119 ms 35164 KB Output is correct
26 Correct 138 ms 35164 KB Output is correct
27 Correct 17 ms 35544 KB Output is correct
28 Correct 16 ms 35544 KB Output is correct
29 Correct 19 ms 35672 KB Output is correct
30 Correct 631 ms 35652 KB Output is correct
31 Correct 729 ms 35616 KB Output is correct
32 Correct 719 ms 35616 KB Output is correct
33 Correct 121 ms 43200 KB Output is correct
34 Correct 122 ms 43812 KB Output is correct
35 Correct 125 ms 41752 KB Output is correct
36 Execution timed out 3060 ms 42952 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34648 KB Output is correct
2 Correct 6 ms 34652 KB Output is correct
3 Correct 5 ms 34568 KB Output is correct
4 Correct 5 ms 34648 KB Output is correct
5 Correct 5 ms 34588 KB Output is correct
6 Correct 5 ms 34904 KB Output is correct
7 Correct 6 ms 34652 KB Output is correct
8 Correct 5 ms 34904 KB Output is correct
9 Correct 6 ms 34648 KB Output is correct
10 Correct 6 ms 34740 KB Output is correct
11 Correct 6 ms 34652 KB Output is correct
12 Correct 6 ms 34652 KB Output is correct
13 Correct 6 ms 34652 KB Output is correct
14 Correct 6 ms 34584 KB Output is correct
15 Correct 5 ms 34652 KB Output is correct
16 Correct 7 ms 34652 KB Output is correct
17 Correct 7 ms 34652 KB Output is correct
18 Correct 7 ms 34652 KB Output is correct
19 Correct 11 ms 35164 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35192 KB Output is correct
22 Correct 146 ms 35064 KB Output is correct
23 Correct 106 ms 35168 KB Output is correct
24 Correct 137 ms 35400 KB Output is correct
25 Correct 119 ms 35164 KB Output is correct
26 Correct 138 ms 35164 KB Output is correct
27 Correct 336 ms 52180 KB Output is correct
28 Correct 297 ms 51248 KB Output is correct
29 Correct 361 ms 54796 KB Output is correct
30 Correct 301 ms 59512 KB Output is correct
31 Execution timed out 3009 ms 54032 KB Time limit exceeded
32 Halted 0 ms 0 KB -