Submission #262397

#	Time	Username	Problem	Language	Result	Execution time	Memory
262397		CaroLinda	Circle selection (APIO18_circle_selection)	C++14	7 / 100	1080 ms	55952 KiB

circle_selection

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a; i < b ; i++)
#define ff first
#define ss second
#define pb emplace_back
#define ll long long
#define mk make_pair
#define sz(x) x.size()
#define pii pair<int,int>
#define mkt make_tuple
#define debug printf

const int MAXN = 5010 ;

using namespace std ;

struct Circle
{

    ll x , y , r ;
    int id ;

    Circle(ll x = 0 , ll y = 0 , ll r  = 0 , int id = 0 ) : x(x) , y(y) , r(r) , id(id) {}
    bool operator < (Circle other) const
    {
        if(r == other.r) return id < other.id ;
        return r > other.r ;
    }

};

int N ;
int sai_para[MAXN] ;
set<Circle> s ;

void process()
{

    Circle ptr = *s.begin() ;

    vector<Circle> toDelete ;

    for(auto e : s )
    {

        ll dist = (ptr.x - e.x) * (ptr.x - e.x) ;
        dist += ( ptr.y - e.y ) * ( ptr.y - e.y ) ;

        ll rad_quad = ptr.r + e.r ;
        rad_quad *= rad_quad ;

        if( dist > rad_quad ) continue ;

        toDelete.pb( e ) ;
        sai_para[ e.id ] = ptr.id ;

    }

    for(auto e : toDelete ) s.erase( s.find(e) ) ;

}

int main()
{

    scanf("%d", &N ) ;
    for(int i = 1 ; i <= N ; i++ )
    {
        ll x , y , r ;
        scanf("%lld %lld %lld", &x, &y, &r ) ;
        s.insert( Circle(x,y,r,i) ) ;
    }

    while( !s.empty() ) process() ;

    lp(i,1,N+1) printf("%d%c", sai_para[i] , " \n"[i == N]) ;

}

Compilation message (stderr)

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

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