Submission #88924

#	Time	Username	Problem	Language	Result	Execution time	Memory
88924		asifthegreat	Circle selection (APIO18_circle_selection)	C++14	7 / 100	178 ms	14176 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 500003;
int ans[N];
bitset<500000>done;

struct point{
    ll x,y,indx,r;
}ara[N];

bool operator<(point a, point b){
    if(a.r != b.r)return a.r > b.r;
    return a.indx < b.indx;
}

bool can_do(int i,int j)
{
    auto a =  ara[i];
    auto b = ara[j];
    ll k = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    if((a.r+b.r)*(a.r+b.r) >= k)return true;return false;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n;i++){
        scanf("%lld %lld %lld",&ara[i].x,&ara[i].y,&ara[i].r);
        ara[i].indx = i;
    }
    sort(ara+1,ara+1+n);
    if(n <= 5000){
        for(int i = 1; i <= n;i++){
            if(done[i])continue;
            for(int j = 1;  j <= n;j++){
                if(!done[j] and can_do(i,j)){
                    ans[ara[j].indx] = ara[i].indx;
                    done[j] = true;
                }
            }
        }
        for(int i = 1; i <= n;i++){
            printf("%d ",ans[i]);
        }puts("");
        exit(0);
    }

    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'bool can_do(int, int)':
circle_selection.cpp:24:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if((a.r+b.r)*(a.r+b.r) >= k)return true;return false;
     ^~
circle_selection.cpp:24:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if((a.r+b.r)*(a.r+b.r) >= k)return true;return false;
                                             ^~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld",&ara[i].x,&ara[i].y,&ara[i].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