Submission #50324

#	Time	Username	Problem	Language	Result	Execution time	Memory
50324		yp155136	Circle selection (APIO18_circle_selection)	C++14	87 / 100	3067 ms	66456 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> Pt;
typedef pair<LL,LL> pii;

#define X first
#define Y second

#define F first
#define S second

inline Pt operator+(const Pt &p1,const Pt &p2)
{
    return make_pair(p1.X+p2.X,p1.Y+p2.Y);
}

inline Pt operator-(const Pt &p1,const Pt &p2)
{
    return make_pair(p1.X-p2.X,p1.Y-p2.Y);
}

inline LL operator*(const Pt &p1,const Pt &p2)
{
    return p1.X*p2.X + p1.Y*p2.Y;
}

inline LL operator^(const Pt &p1,const Pt &p2)
{
    return p1.X*p2.Y - p1.Y*p2.X;
}

int n;

const int N = 300006;

int a[N];

Pt p[N];
LL r[N];

bool vis[N];

void solve_n2()
{
    for (int i=1;n>=i;i++)
    {
        scanf("%lld %lld %lld",&p[i].X,&p[i].Y,&r[i]);
    }
    for (int i=1;n>=i;i++)
    {
        //find the max radius
        int mx_r = 0;
        int mx_id = -1;
        for (int j=1;n>=j;j++)
        {
            if (!vis[j] && r[j] > mx_r)
            {
                mx_r = r[j];
                mx_id = j;
            }
        }
        if (mx_id == -1) break;
        for (int j=1;n>=j;j++)
        {
            if (vis[j]) continue;
            if (( (p[j]-p[mx_id])*(p[j]-p[mx_id]) ) <= (r[mx_id] + r[j])*(r[mx_id]+r[j]) )
            {
                a[j] = mx_id;
                vis[j] = true;
            }
        }
    }
    for (int i=1;n>=i;i++)
    {
        if (i!=1) printf(" ");
        printf("%d",a[i]);
    }
    puts("");
}

set<pii> R_x,L_x,xx;  //store x[i]+r,x[i]-r

void del_index(int i,int a_val)
{
    a[i] = a_val;
    vis[i] = true;
    L_x.erase(L_x.find(make_pair(p[i].X-r[i],i)));
    R_x.erase(R_x.find(make_pair(p[i].X+r[i],i)));
    xx.erase(xx.find(make_pair(p[i].X,i)));
}

void solve_y0()
{
    priority_queue<pii> pq;
    for (int i=1;n>=i;i++)
    {
        pq.push(make_pair(r[i],-i));
        R_x.insert(make_pair(p[i].X+r[i],i));
        L_x.insert(make_pair(p[i].X-r[i],i));
        xx.insert(make_pair(p[i].X,i));
    }
    while (!pq.empty())
    {
        pii pp=pq.top();
        pq.pop();
        int ii = -pp.S;
        if (vis[ii]) continue;
        //cout << "ii = " << ii << endl;
        auto iter_pre=xx.lower_bound(make_pair(p[ii].X,ii));
        vector<int> del_id;
        //delete center in (x-r,x+r)
        auto iter_end = iter_pre;
        ++iter_end;
        while ((*iter_pre).X >= p[ii].X-r[ii])
        {
            pii p=(*iter_pre);
            //cout << "p.S = " << p.S << endl;
            del_id.push_back(p.S);
            if (iter_pre == xx.begin()) break;
            --iter_pre;
        }
        //cout << "finish first while " << endl;
        while (iter_end != xx.end() && (*iter_end).X <= p[ii].X+r[ii])
        {
            pii p=(*iter_end);
            //cout << "p.SS = " << p.S <<endl;
            del_id.push_back(p.S);
            ++iter_end;
        }
        //cout << "finish second while" << endl;
        for (int i:del_id)
        {
            //cout << "i = " << i << endl;
            del_index(i,ii);
        }
        //cout << "finish delete" <<endl;
        del_id.clear();
        //now, let us search x[i]-r[i]  <= x[j] + r[j] <= x[i] + r[i]
        auto iter1 = R_x.lower_bound(make_pair(p[ii].X-r[ii],-1));
        while (iter1 != R_x.end() && (*iter1).F <= p[ii].X+r[ii])
        {
            pii p=(*iter1);
            del_id.push_back((p.S));
            iter1++;
        }
        for (int i:del_id)
        {
            del_index(i,ii);
        }
        del_id.clear();
        //now, let us search x[i]-r[i]  <= x[j] - r[j] <= x[i] + r[i]
        auto iter2 = L_x.lower_bound(make_pair(p[ii].X-r[ii],-1));
        while (iter2 != L_x.end() && (*iter2).F <= p[ii].X+r[ii])
        {
            pii p=(*iter2);
            del_id.push_back(p.S);
            iter2++;
        }
        for (int i:del_id)
        {
            del_index(i,ii);
        }
        del_id.clear();
    }
    for (int i=1;n>=i;i++)
    {
        if (i!=1) printf(" ");
        printf("%d",a[i]);
    }
    puts("");
}

unordered_set<int> st[N];
map<pii,int> mp;

int dx[25] = {-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int dy[25] = {-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};

bool okay_r_same(int i,int j)
{
    if ( ( (p[i]-p[j])*(p[i]-p[j]) ) <= (r[i]+r[j])*(r[i]+r[j]) )
    {
        a[j] = i;
        vis[j] = true;
        return true;
    }
    return false;
}

void solve_r_same()
{
    LL M = r[1];
    int _=0;
    for (int i=1;n>=i;i++)
    {
        pii id=make_pair(p[i].X/M,p[i].Y/M);
        if (mp.find(id) == mp.end())
        {
            mp[id] = (++_);
        }
        st[ mp[id] ].insert(i);
    }
    for (int i=1;n>=i;i++)
    {
        if (vis[i]) continue;
        pii id=make_pair(p[i].X/M,p[i].Y/M);
        for (int k=0;25>k;k++)
        {
            pii h = id+make_pair(dx[k],dy[k]);
            auto iter=mp.find(h);
            if (iter == mp.end()) continue;
            int __ = (*iter).S;
            vector<int> del_id;
            for (int j:st[__])
            {
                if (okay_r_same(i,j))
                {
                    del_id.push_back(j);
                }
            }
            for (int j:del_id)
            {
                st[__].erase(j);
            }
        }
    }
    for (int i=1;n>=i;i++)
    {
        if (i!=1) printf(" ");
        printf("%d",a[i]);
    }
    puts("");
}

//unordered_set<int> alive_index;

const int G = 1024;

unordered_map<LL,LL> mp2;

inline LL to_LL(pii p)
{
    return (p.F+1000000001+G)*(2000000001+G) + (p.S + 1000000001+G);
}

int lc[N],rc[N];  //linked list for alive things

void build_graph(int R)
{
    mp2.clear();
    int _=0;
    for (int i=rc[0];i!=n+1;i=rc[i])
    {
        pii id = make_pair(p[i].X/R,p[i].Y/R);
        if (mp2.find(to_LL(id)) == mp2.end())
        {
            _++;
            st[_].clear();
            mp2[to_LL(id)] = _;
        }
        st[ mp2[ to_LL(id) ] ].insert(i);
    }
}

//const int G = 7122;

inline void out(int x)
{
    if (x > 9)
    {
        out(x/10);
    }
    putchar(x%10 + '0');
}

double sqrt_num[102];

void build()
{
    for (int i=0;102>i;i++)
    {
        sqrt_num[i] = sqrt(i);
    }
}

void solve()
{
    priority_queue<pii> pq;
    rc[0] = 1;
    for (int i=1;n>=i;i++)
    {
        pq.push(make_pair(r[i],-i));
        //alive_index.insert(i);
        lc[i] = i-1;
        rc[i] = i+1;
    }
    int cnt = -1;
    LL R = -1;
    int now=0;
    while (!pq.empty())
    {
        pii pp=pq.top();
        pq.pop();
        int ii=-pp.S;
        ++now;
        if (vis[ii]) continue;
        //if (now%1000 == 0) cout << "now = " << now << endl;
        --cnt;
        if (R == -1 || cnt < 0 && r[ii]*100 < R)
        {
            R = r[ii];
            build_graph(R);
            cnt = G;
        }
        pii id=make_pair(p[ii].X/R,p[ii].Y/R);
        for (int k=0;25>k;k++)
        {
            int ddx = abs(dx[k])-1 , ddy = abs(dy[k])-1;
            ddx = max(ddx,0);
            ddy = max(ddy,0);
            if (sqrt_num[ddx*ddx + ddy*ddy]*R+0.0001 > 2*r[ii]) continue;
            pii h = id+make_pair(dx[k],dy[k]);
            auto iter=mp2.find( to_LL(h) );
            if (iter == mp2.end()) continue;
            int __ = (*iter).S;
            vector<int> del_id;
            for (int j:st[__])
            {
                if (okay_r_same(ii,j))
                {
                    del_id.push_back(j);
                }
            }
            for (int j:del_id)
            {
                st[__].erase(j);
                lc[ rc[j] ] = lc[j];
                rc[ lc[j] ] = rc[j];
                //alive_index.erase(j);
            }
        }
    }
    for (int i=1;n>=i;i++)
    {
        out(a[i]);
        if (i == n) putchar('\n');
        else putchar(' ');
        //(i==n?putchar('\n'):putchar(' '));
        //if (i!=1) printf(" ");
        //printf("%d",a[i]);
    }
    //puts("");
}

//#define getchar_unlocked getchar

inline int rit()
{
    int ret=0;
    int f=1;
    char c;
    do {
        c = getchar_unlocked();
        if (c == '-') f = -1;
    } while (c < '0' || c>'9');
    do {
        ret *= 10;
        ret += (c-'0');
        c = getchar_unlocked();
    } while ('0' <= c && c <= '9');
    return f*ret;
}

int main ()
{
    //out(0);
    //out(1234);
    //out(12);
    //int n;
    //scanf("%d",&n);
    n = rit();
    if (n <= 5000)
    {
        solve_n2();
        return 0;
    }
    bool y_0 = true;
    bool r_same=true;
    for (int i=1;n>=i;i++)
    {
        p[i].X = rit() + G;
        p[i].Y = rit() + G;
        r[i] = rit();
        //scanf("%lld %lld %lld",&p[i].X,&p[i].Y,&r[i]);
        y_0 &= (p[i].Y == 0);
        r_same &= (r[i]==r[1]);
    }
    if (y_0)
    {
        solve_y0();
        return 0;
    }
    if (r_same)
    {
        solve_r_same();
        return 0;
    }
    solve();
}

/*
5
3 0 2
2 0 1
5 0 2
0 0 1
6 0 2
*/

/*
3
0 0 3
1 1 3
6 6 3
*/

Compilation message (stderr)

circle_selection.cpp: In function 'void solve()':
circle_selection.cpp:311:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (R == -1 || cnt < 0 && r[ii]*100 < R)
                        ~~~~~~~~^~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void solve_n2()':
circle_selection.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld",&p[i].X,&p[i].Y,&r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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