oj.uz

Submission #88924

# Submission time Handle Problem Language Result Execution time Memory
88924 2018-12-09T20:59:03 Z asifthegreat Circle selection (APIO18_circle_selection) C++14
7 / 100
 178 ms 14176 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 648 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 808 KB Output is correct
12 Correct 2 ms 808 KB Output is correct
13 Correct 2 ms 808 KB Output is correct
14 Correct 2 ms 808 KB Output is correct
15 Correct 2 ms 808 KB Output is correct
16 Correct 3 ms 808 KB Output is correct
17 Correct 3 ms 848 KB Output is correct
18 Correct 3 ms 848 KB Output is correct
19 Correct 6 ms 1132 KB Output is correct
20 Correct 6 ms 1284 KB Output is correct
21 Correct 6 ms 1436 KB Output is correct
22 Correct 128 ms 1668 KB Output is correct
23 Correct 60 ms 1748 KB Output is correct
24 Correct 56 ms 1984 KB Output is correct
25 Correct 58 ms 2036 KB Output is correct
26 Correct 58 ms 2224 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 11416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11416 KB Output is correct
2 Incorrect 65 ms 11416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 14176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 648 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 808 KB Output is correct
12 Correct 2 ms 808 KB Output is correct
13 Correct 2 ms 808 KB Output is correct
14 Correct 2 ms 808 KB Output is correct
15 Correct 2 ms 808 KB Output is correct
16 Correct 3 ms 808 KB Output is correct
17 Correct 3 ms 848 KB Output is correct
18 Correct 3 ms 848 KB Output is correct
19 Correct 6 ms 1132 KB Output is correct
20 Correct 6 ms 1284 KB Output is correct
21 Correct 6 ms 1436 KB Output is correct
22 Correct 128 ms 1668 KB Output is correct
23 Correct 60 ms 1748 KB Output is correct
24 Correct 56 ms 1984 KB Output is correct
25 Correct 58 ms 2036 KB Output is correct
26 Correct 58 ms 2224 KB Output is correct
27 Incorrect 8 ms 14176 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 648 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 808 KB Output is correct
12 Correct 2 ms 808 KB Output is correct
13 Correct 2 ms 808 KB Output is correct
14 Correct 2 ms 808 KB Output is correct
15 Correct 2 ms 808 KB Output is correct
16 Correct 3 ms 808 KB Output is correct
17 Correct 3 ms 848 KB Output is correct
18 Correct 3 ms 848 KB Output is correct
19 Correct 6 ms 1132 KB Output is correct
20 Correct 6 ms 1284 KB Output is correct
21 Correct 6 ms 1436 KB Output is correct
22 Correct 128 ms 1668 KB Output is correct
23 Correct 60 ms 1748 KB Output is correct
24 Correct 56 ms 1984 KB Output is correct
25 Correct 58 ms 2036 KB Output is correct
26 Correct 58 ms 2224 KB Output is correct
27 Incorrect 178 ms 11416 KB Output isn't correct
28 Halted 0 ms 0 KB -