Submission #1260090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260090		hamanp87	Circle selection (APIO18_circle_selection)	C++20	100 / 100	940 ms	18928 KiB

circle_selection

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

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")

#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;

const int inf=1e9,mod=1e9+7,neginf=-1e9;
const double PI=acos(-1);

struct Circle
{
    ll x,y,r;
};

int n;
ll Cel=LLONG_MAX;
veci ans;
vector<array<ll,3>> Cmp;
vector<Circle> Cs;

inline bool intersect(const Circle &a,const Circle &b)
{
    ll dx=a.x-b.x;
    ll dy=a.y-b.y;
    ll R=a.r+b.r;

    return dx*dx+dy*dy<=R*R;
}

inline ll fl(ll a,ll b)
{
    if(b<=0)
        b=1;
    if(a>=0)
        return a/b;
    return -((-a+b-1)/b);
}

inline bool cmpa(const array<ll,3> &a,const array<ll,3> &b)
{
    if(a[0]!=b[0])
        return a[0]<b[0];
    if(a[1]!=b[1])
        return a[1]<b[1];
    return a[2]<b[2];
}

inline bool cmpc(int a,int b)
{
    if(Cs[a].r==Cs[b].r)
        return a<b;
    return Cs[a].r>Cs[b].r;
}

size_t LBS(const vector<array<ll,3>> &v,const array<ll,3> &k)
{
    size_t L=0,R=v.size();
    while(L<R)
    {
        size_t mid=(L+R)>>1;
        if(cmpa(v[mid],k))
            L=mid+1;
        else
            R=mid;
    }

    return L;
}

void RB(ll nr)
{
    Cel=max(1LL,2*nr);
    Cmp.clear();
    Cmp.reserve(n);
    for(int i=0;i<n;i++)
    {
        if(ans[i]==-1)
        {
            ll cx=fl(Cs[i].x,Cel);
            ll cy=fl(Cs[i].y,Cel);
            Cmp.pub({cx,cy,i});
        }
    }

    sort(all(Cmp),cmpa);
}

void solve()
{
    cin>>n;
    Cs.assign(n,{});
    for(int i=0;i<n;i++)
        cin>>Cs[i].x>>Cs[i].y>>Cs[i].r;

    ans.assign(n,-1);

    veci ord(n);
    iota(all(ord),0);
    sort(all(ord),cmpc);

    for(int ind:ord)
    {
        if(ans[ind]!=-1)
            continue;

        if(Cs[ind].r*4<Cel)
            RB(Cs[ind].r);

        ans[ind]=ind;
        ll cx=fl(Cs[ind].x,Cel);
        ll cy=fl(Cs[ind].y,Cel);

        for(ll x=cx-1;x<cx+2;x++)
        {
            array<ll,3> k={x,cy-1,-1};
            size_t it=LBS(Cmp,k);
            while(it<Cmp.size() and Cmp[it][0]==x and Cmp[it][1]<=cy+1)
            {
                int j=(int)Cmp[it][2];
                if(ans[j]==-1 and intersect(Cs[j],Cs[ind]))
                    ans[j]=ind;
                it++;
            }
        }
    }

    for(int i=0;i<n;i++)
        cout<<ans[i]+1<<' ';
    cout<<"\n";
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    //ifstream fin("in.txt");
    //ofstream fout("out.txt");

    int t=1;
    //cin>>t;
    while(t--)
    {
        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