Submission #393998

#	Time	Username	Problem	Language	Result	Execution time	Memory
393998		79brue	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3068 ms	42116 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Circle{
    ll x, y, r; int idx;
    Circle(ll x, ll y, ll r, int idx): x(x), y(y), r(r), idx(idx){}
    bool touch(const Circle &nxt)const{
        return (x-nxt.x) * (x-nxt.x) + (y-nxt.y) * (y-nxt.y) <= (r+nxt.r) * (r+nxt.r);
    }
    bool operator<(const Circle &nxt)const{
        if(r!=nxt.r) return r>nxt.r;
        return idx<nxt.idx;
    }
};
vector<Circle> vec;
vector<Circle> nvec;

int n;
int ans[300002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        ll x, y, r;
        scanf("%lld %lld %lld", &x, &y, &r);
        vec.push_back(Circle(x, y, r, i));
    }
    sort(vec.begin(), vec.end());
    while(!vec.empty()){
        nvec.clear();
        for(auto x: vec){
            if(x.touch(vec[0])) ans[x.idx] = vec[0].idx;
            else nvec.push_back(x);
        }
        vec = nvec;
    }
    for(int i=1; i<=n; i++){
        printf("%d ", ans[i]);
    }
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         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