Submission #120773

#	Time	Username	Problem	Language	Result	Execution time	Memory
120773		_demon_	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3040 ms	74208 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
int n;
int ans[100009];
struct xxx{
    long double r,x,y,id;
};
bool operator < (xxx a,xxx b){
    if(a.r==b.r) return a.id>b.id;
    return a.r<b.r;
}
set<xxx> s;
int main(){
    cin>>n;
    for(long double i=0;i<n;i++){
        long double r,x,y;
        cin>>x>>y>>r;
        s.insert({r,x,y,i});
    }
    while(s.size()>0){
        vector<xxx>v;
        v.clear();
        long double r=s.rbegin()->r;
        long double x=s.rbegin()->x;
        long double y=s.rbegin()->y;
        long double id=s.rbegin()->id;
        ans[(int)id]=id+1;
        s.erase({r,x,y,id});
        for(set<xxx>::iterator i=s.begin();i!=s.end();i++){
            long double rr=i->r;
            long double xx=i->x;
            long double yy=i->y;
            long double idd=i->id;
            long double dis=sqrt(pow(abs(xx-x),2)+pow(abs(yy-y),2));
            if(dis<=rr+r){
                v.push_back({rr,xx,yy,idd});
            }
       }
        for(int i=0;i<v.size();i++){
            long double rr=v[i].r;
            long double xx=v[i].x;
            long double yy=v[i].y;
            long double idd=v[i].id;
            s.erase({rr,xx,yy,idd});
            ans[(int)idd]=id+1;
        }
    }
    for(int i=0;i<n;i++)cout<<ans[i]<<" ";
    cout<<endl;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++){
                     ~^~~~~~~~~

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