oj.uz

Submission #866313

# Submission time Handle Problem Language Result Execution time Memory
866313 2023-10-25T21:00:15 Z danikoynov Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 56248 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 = max(0, cor_x - 2); i < min((int)field.size(), cor_x + 3); 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: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: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 5 ms 34652 KB Output is correct
3 Correct 6 ms 34592 KB Output is correct
4 Correct 5 ms 34652 KB Output is correct
5 Correct 5 ms 34652 KB Output is correct
6 Correct 5 ms 34556 KB Output is correct
7 Correct 5 ms 34652 KB Output is correct
8 Correct 5 ms 34652 KB Output is correct
9 Correct 5 ms 34652 KB Output is correct
10 Correct 6 ms 34588 KB Output is correct
11 Correct 6 ms 34748 KB Output is correct
12 Correct 6 ms 34772 KB Output is correct
13 Correct 5 ms 34652 KB Output is correct
14 Correct 5 ms 34768 KB Output is correct
15 Correct 6 ms 34652 KB Output is correct
16 Correct 6 ms 34652 KB Output is correct
17 Correct 7 ms 34908 KB Output is correct
18 Correct 6 ms 34652 KB Output is correct
19 Correct 10 ms 35416 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35068 KB Output is correct
22 Correct 56 ms 35056 KB Output is correct
23 Correct 55 ms 35024 KB Output is correct
24 Correct 57 ms 34908 KB Output is correct
25 Correct 56 ms 35120 KB Output is correct
26 Correct 57 ms 34904 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 52156 KB Output is correct
2 Correct 310 ms 49456 KB Output is correct
3 Correct 291 ms 46876 KB Output is correct
4 Correct 294 ms 51264 KB Output is correct
5 Correct 2784 ms 49684 KB Output is correct
6 Execution timed out 3036 ms 56248 KB Time limit exceeded
7 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 3082 ms 40068 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 3055 ms 50620 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 5 ms 34652 KB Output is correct
3 Correct 6 ms 34592 KB Output is correct
4 Correct 5 ms 34652 KB Output is correct
5 Correct 5 ms 34652 KB Output is correct
6 Correct 5 ms 34556 KB Output is correct
7 Correct 5 ms 34652 KB Output is correct
8 Correct 5 ms 34652 KB Output is correct
9 Correct 5 ms 34652 KB Output is correct
10 Correct 6 ms 34588 KB Output is correct
11 Correct 6 ms 34748 KB Output is correct
12 Correct 6 ms 34772 KB Output is correct
13 Correct 5 ms 34652 KB Output is correct
14 Correct 5 ms 34768 KB Output is correct
15 Correct 6 ms 34652 KB Output is correct
16 Correct 6 ms 34652 KB Output is correct
17 Correct 7 ms 34908 KB Output is correct
18 Correct 6 ms 34652 KB Output is correct
19 Correct 10 ms 35416 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35068 KB Output is correct
22 Correct 56 ms 35056 KB Output is correct
23 Correct 55 ms 35024 KB Output is correct
24 Correct 57 ms 34908 KB Output is correct
25 Correct 56 ms 35120 KB Output is correct
26 Correct 57 ms 34904 KB Output is correct
27 Correct 17 ms 35288 KB Output is correct
28 Correct 16 ms 35164 KB Output is correct
29 Correct 16 ms 35284 KB Output is correct
30 Correct 228 ms 35320 KB Output is correct
31 Correct 227 ms 35352 KB Output is correct
32 Correct 232 ms 35356 KB Output is correct
33 Correct 149 ms 40648 KB Output is correct
34 Correct 121 ms 41924 KB Output is correct
35 Correct 124 ms 38948 KB Output is correct
36 Execution timed out 3069 ms 40248 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 5 ms 34652 KB Output is correct
3 Correct 6 ms 34592 KB Output is correct
4 Correct 5 ms 34652 KB Output is correct
5 Correct 5 ms 34652 KB Output is correct
6 Correct 5 ms 34556 KB Output is correct
7 Correct 5 ms 34652 KB Output is correct
8 Correct 5 ms 34652 KB Output is correct
9 Correct 5 ms 34652 KB Output is correct
10 Correct 6 ms 34588 KB Output is correct
11 Correct 6 ms 34748 KB Output is correct
12 Correct 6 ms 34772 KB Output is correct
13 Correct 5 ms 34652 KB Output is correct
14 Correct 5 ms 34768 KB Output is correct
15 Correct 6 ms 34652 KB Output is correct
16 Correct 6 ms 34652 KB Output is correct
17 Correct 7 ms 34908 KB Output is correct
18 Correct 6 ms 34652 KB Output is correct
19 Correct 10 ms 35416 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35068 KB Output is correct
22 Correct 56 ms 35056 KB Output is correct
23 Correct 55 ms 35024 KB Output is correct
24 Correct 57 ms 34908 KB Output is correct
25 Correct 56 ms 35120 KB Output is correct
26 Correct 57 ms 34904 KB Output is correct
27 Correct 295 ms 52156 KB Output is correct
28 Correct 310 ms 49456 KB Output is correct
29 Correct 291 ms 46876 KB Output is correct
30 Correct 294 ms 51264 KB Output is correct
31 Correct 2784 ms 49684 KB Output is correct
32 Execution timed out 3036 ms 56248 KB Time limit exceeded
33 Halted 0 ms 0 KB -