Submission #866321

#	Time	Username	Problem	Language	Result	Execution time	Memory
866321		danikoynov	Circle selection (APIO18_circle_selection)	C++14	100 / 100	894 ms	79732 KiB

circle_selection

#include<bits/stdc++.h>
#define endl '\n'

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);

    set < pair < int, int > > active;
    for (int i = 1; i <= n; i ++)
        active.insert({c[i].radius, -i});
    while(!active.empty())
    {

        int idx = -active.rbegin() -> second; 
        
        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;
                    active.erase({field[i][j].radius, -field[i][j].idx});
                }
            }
        }

    }

    for (int i = 1; i <= n; i ++)
        std::cout << parent[i] << " ";
    std::cout << endl;
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
void solve()
{
    input();
    sort_arrays();
    simulate();
}
 
int main()
{
    speed();
    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 (stderr)

circle_selection.cpp: In function 'void simulate()':
circle_selection.cpp:150:34: warning: unused variable 'cor_y' [-Wunused-variable]
  150 |         int cor_x = comp[idx].x, cor_y = comp[idx].y;
      |                                  ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13