oj.uz

Submission #866316

# Submission time Handle Problem Language Result Execution time Memory
866316 2023-10-25T21:09:31 Z danikoynov Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 53288 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 ++)
        {
            int lf = 0, rf = (int)(field[i].size()) - 1;
            while(lf <= rf)
            {
                int mf = (lf + rf) / 2;
                if (c[idx].centre.y / last_block - field[i][mf].centre.y / last_block > 2)
                    lf = mf + 1;
                else   
                    rf = mf - 1;
            }

            int lb = lf;

            lf = 0;
            rf = (int)(field[i].size()) - 1;
            while(lf <= rf)
            {
                int mf = (lf + rf) / 2;
                if (field[i][mf].centre.y / last_block - c[idx].centre.y / last_block > 2)
                    rf = mf - 1;
                else
                    lf = mf + 1;
            }

            int rb = rf;
            for (int j = lb; j <= rb; 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 ++)
        std::cout << parent[i] << " ";
    std::cout << std::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:34: warning: unused variable 'cor_y' [-Wunused-variable]
  157 |         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 34652 KB Output is correct
2 Correct 5 ms 34652 KB Output is correct
3 Correct 5 ms 34652 KB Output is correct
4 Correct 5 ms 34652 KB Output is correct
5 Correct 5 ms 34648 KB Output is correct
6 Correct 5 ms 34648 KB Output is correct
7 Correct 5 ms 34652 KB Output is correct
8 Correct 5 ms 34648 KB Output is correct
9 Correct 5 ms 34652 KB Output is correct
10 Correct 6 ms 34556 KB Output is correct
11 Correct 5 ms 34652 KB Output is correct
12 Correct 5 ms 34652 KB Output is correct
13 Correct 5 ms 34568 KB Output is correct
14 Correct 5 ms 34648 KB Output is correct
15 Correct 5 ms 34652 KB Output is correct
16 Correct 7 ms 34652 KB Output is correct
17 Correct 6 ms 34652 KB Output is correct
18 Correct 7 ms 34652 KB Output is correct
19 Correct 11 ms 35032 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35164 KB Output is correct
22 Correct 58 ms 35056 KB Output is correct
23 Correct 58 ms 35032 KB Output is correct
24 Correct 58 ms 34904 KB Output is correct
25 Correct 62 ms 35116 KB Output is correct
26 Correct 59 ms 35092 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 53288 KB Output is correct
2 Correct 316 ms 51500 KB Output is correct
3 Correct 304 ms 47908 KB Output is correct
4 Correct 301 ms 52520 KB Output is correct
5 Correct 2794 ms 49468 KB Output is correct
6 Execution timed out 3025 ms 52532 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 3088 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 3037 ms 51504 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 34652 KB Output is correct
2 Correct 5 ms 34652 KB Output is correct
3 Correct 5 ms 34652 KB Output is correct
4 Correct 5 ms 34652 KB Output is correct
5 Correct 5 ms 34648 KB Output is correct
6 Correct 5 ms 34648 KB Output is correct
7 Correct 5 ms 34652 KB Output is correct
8 Correct 5 ms 34648 KB Output is correct
9 Correct 5 ms 34652 KB Output is correct
10 Correct 6 ms 34556 KB Output is correct
11 Correct 5 ms 34652 KB Output is correct
12 Correct 5 ms 34652 KB Output is correct
13 Correct 5 ms 34568 KB Output is correct
14 Correct 5 ms 34648 KB Output is correct
15 Correct 5 ms 34652 KB Output is correct
16 Correct 7 ms 34652 KB Output is correct
17 Correct 6 ms 34652 KB Output is correct
18 Correct 7 ms 34652 KB Output is correct
19 Correct 11 ms 35032 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35164 KB Output is correct
22 Correct 58 ms 35056 KB Output is correct
23 Correct 58 ms 35032 KB Output is correct
24 Correct 58 ms 34904 KB Output is correct
25 Correct 62 ms 35116 KB Output is correct
26 Correct 59 ms 35092 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 35288 KB Output is correct
30 Correct 235 ms 35328 KB Output is correct
31 Correct 235 ms 35356 KB Output is correct
32 Correct 235 ms 35604 KB Output is correct
33 Correct 120 ms 40388 KB Output is correct
34 Correct 119 ms 41668 KB Output is correct
35 Correct 121 ms 38836 KB Output is correct
36 Execution timed out 3076 ms 40244 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 34652 KB Output is correct
2 Correct 5 ms 34652 KB Output is correct
3 Correct 5 ms 34652 KB Output is correct
4 Correct 5 ms 34652 KB Output is correct
5 Correct 5 ms 34648 KB Output is correct
6 Correct 5 ms 34648 KB Output is correct
7 Correct 5 ms 34652 KB Output is correct
8 Correct 5 ms 34648 KB Output is correct
9 Correct 5 ms 34652 KB Output is correct
10 Correct 6 ms 34556 KB Output is correct
11 Correct 5 ms 34652 KB Output is correct
12 Correct 5 ms 34652 KB Output is correct
13 Correct 5 ms 34568 KB Output is correct
14 Correct 5 ms 34648 KB Output is correct
15 Correct 5 ms 34652 KB Output is correct
16 Correct 7 ms 34652 KB Output is correct
17 Correct 6 ms 34652 KB Output is correct
18 Correct 7 ms 34652 KB Output is correct
19 Correct 11 ms 35032 KB Output is correct
20 Correct 11 ms 35164 KB Output is correct
21 Correct 11 ms 35164 KB Output is correct
22 Correct 58 ms 35056 KB Output is correct
23 Correct 58 ms 35032 KB Output is correct
24 Correct 58 ms 34904 KB Output is correct
25 Correct 62 ms 35116 KB Output is correct
26 Correct 59 ms 35092 KB Output is correct
27 Correct 302 ms 53288 KB Output is correct
28 Correct 316 ms 51500 KB Output is correct
29 Correct 304 ms 47908 KB Output is correct
30 Correct 301 ms 52520 KB Output is correct
31 Correct 2794 ms 49468 KB Output is correct
32 Execution timed out 3025 ms 52532 KB Time limit exceeded
33 Halted 0 ms 0 KB -