Submission #348336

#	Time	Username	Problem	Language	Result	Execution time	Memory
348336		denkendoemeer	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1476 ms	27352 KiB

circle_selection

#include<bits/stdc++.h>
using namespace std;
struct cerc
{
    int x,y,r,id;
    bool operator < (const cerc &a) const
    {
        return make_pair(x,y)<make_pair(a.x,a.y);
    }
}v[300005],orig[300005];
const int nr=1e9+100;
int ans[300005];
bool inter(cerc a,cerc b)
{
    int dx=a.x-b.x,dy=a.y-b.y,dr=a.r+b.r;
    if (1LL*dx*dx+1LL*dy*dy<=1LL*dr*dr)
        return 1;
    return 0;
}
int cmp(const cerc &a,const cerc &b)
{
    return make_pair(-a.r,a.id)<make_pair(-b.r,b.id);
}
vector<cerc>aux;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i,off,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].r);
        v[i].x+=nr;
        v[i].y+=nr;
        v[i].id=i+1;
        orig[i+1]=v[i];
    }
    sort(v,v+n,cmp);
    for(i=30;i>=1;i--){
        int st,dr;
        st=1<<(i-1);
        dr=(1<<i)-1;
        aux.clear();
        for(j=0;j<n;j++)
            if (ans[v[j].id]==0 && v[j].r<=dr)
                aux.push_back({v[j].x>>i,v[j].y>>i,v[j].r,v[j].id});
        sort(aux.begin(),aux.end());
        for(j=0;j<n;j++)
            if (ans[v[j].id]==0 && v[j].r>=st && v[j].r<=dr){
                for(off=-2;off<=2;off++){
                    int auxx=(v[j].x>>i)+off,auxy=(v[j].y>>i)-2;
                    auto it=lower_bound(aux.begin(),aux.end(),(cerc){auxx,auxy,-1,-1})-aux.begin();
                    while(it<aux.size() && make_pair(aux[it].x,aux[it].y)<=make_pair(auxx,auxy+4)){
                        if (inter(orig[aux[it].id],v[j]) && ans[aux[it].id]==0)
                            ans[aux[it].id]=v[j].id;
                        it++;
                    }
                }
            }
    }
    for(i=1;i<=n;i++)
        printf("%d ",ans[i]);
return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:53:29: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<cerc>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                     while(it<aux.size() && make_pair(aux[it].x,aux[it].y)<=make_pair(auxx,auxy+4)){
      |                           ~~^~~~~~~~~~~
circle_selection.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |         scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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