Submission #698881

#	Time	Username	Problem	Language	Result	Execution time	Memory
698881		milisav	Circle selection (APIO18_circle_selection)	C++14	34 / 100	1151 ms	23900 KiB

circle_selection

#include<bits/stdc++.h>
#define maxn 400000
using namespace std;
int n;
int el[maxn];
int x[maxn];
int y[maxn];
int rev[maxn];
int radius[maxn];
pair<pair<int,int>,pair<int,int> > circ[maxn];
vector<pair<pair<int,int>,int> > v;
set<pair<int,int> > s;
inline bool intersect(int i,int j) {
    return 1ll*(x[i]-x[j])*(x[i]-x[j])+1ll*(y[i]-y[j])*(y[i]-y[j])<=1ll*(radius[i]+radius[j])*(radius[i]+radius[j]);
}
void dc(int l,int r) {
    if(l==r) return;
    int m=(l+r)/2;
    dc(l,m);
    //cout<<l<<" "<<m<<" "<<r<<endl;
    for(int i=l;i<=r;i++) {
        int ind=circ[i].first.second;
        if(el[ind]==ind) {
            //cout<<ind<<endl;
            if(i<=m) {
                v.push_back({{x[ind]-radius[ind],0},ind});
                v.push_back({{x[ind]+radius[ind],2},ind});
            }
            else {
                v.push_back({{x[ind]-radius[ind],1},ind});
                v.push_back({{x[ind]+radius[ind],1},ind});
            }
        }
    }
    sort(v.begin(),v.end());
    for(auto p:v) {
        int xc=p.first.first;
        int ind=p.second;
        int pos=rev[ind];
        if(pos<=m) {
            //cout<<ind<<" "<<pos<<endl;
            if(xc == x[ind]-radius[ind]) s.insert({y[ind],ind});
            else s.erase({y[ind],ind});
        }
        else {
            if(s.empty()) continue;
            set<pair<int,int> >::iterator it=s.lower_bound({y[ind],-1});
            set<pair<int,int> >::iterator st=it;
            int co=0;
            int i=0;
            //cout<<ind<<" "<<pos<<endl;
            while(it!=s.end() && i<=co) {
                int jnd=(*it).second;
                if(rev[jnd]<rev[el[ind]] && intersect(ind,jnd)) {
                    el[ind]=jnd;
                }
                it++;
                i++;
            }
            it=st;
            if(it==s.begin()) continue;
            i=0;
            do {
                it--;
                int jnd=(*it).second;
                if(rev[jnd]<rev[el[ind]] && intersect(ind,jnd)) {
                    el[ind]=jnd;
                }
                i++;
            } while(it!=s.begin() && i<=co);
        }
    }
    s.clear();
    v.clear();
    dc(m+1,r);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d %d %d",&x[i],&y[i],&radius[i]);
        circ[i]={{-radius[i],i},{x[i],y[i]}};
        el[i]=i;
    }
    sort(circ+1,circ+n+1);
    for(int i=1;i<=n;i++) {
        rev[circ[i].first.second]=i;
        //cout<<circ[i].first.second<<" ";
    }
    //cout<<endl;
    dc(1,n);
    for(int i=1;i<=n;i++) {
        printf("%d ",el[i]);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d %d %d",&x[i],&y[i],&radius[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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