Submission #50325

#	Time	Username	Problem	Language	Result	Execution time	Memory
50325		yp155136	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2611 ms	69448 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];

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

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;
}
//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;
    }
    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;
        if (R == -1 || r[ii]*2 < R)
        {
            R = r[ii];
            build_graph(R);
        }
        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];
            }
        }
    }
    for (int i=1;n>=i;i++)
    {
        out(a[i]);
        if (i == n) putchar('\n');
        else putchar(' ');
    }
}

//#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 ()
{
    n = rit();
    for (int i=1;n>=i;i++)
    {
        p[i].X = rit() + G;
        p[i].Y = rit() + G;
        r[i] = rit();
    }
    solve();
}

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