oj.uz

Submission #291319

# Submission time Handle Problem Language Result Execution time Memory
291319 2020-09-05T05:43:44 Z blue Circle selection (APIO18_circle_selection) C++11
7 / 100
 3000 ms 18916 KB 
#include <iostream>
#include <vector>
using namespace std;

long long sq(long long a)
{
    return a*a;
}

//7 pts: n <= 5000

int main()
{
    long long n;
    cin >> n;

    long long x[n+1], y[n+1], r[n+1];
    for(long long i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];

    vector<long long> kill(n+1, 0);
    long long c;
    r[0] = 0;
    while(1)
    {
        c = 0;
        for(long long i = 1; i <= n; i++) if(!kill[i] && r[i] > r[c]) c = i;
        if(!c) break;
        for(long long i = 1; i <= n; i++)
            if(!kill[i] && sq(x[i] - x[c]) + sq(y[i] - y[c]) <= sq(r[i] + r[c]))
                kill[i] = c;
    }
    for(long long i = 1; i <= n; i++) cout << kill[i] << ' ';
    cout << '\n';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 14 ms 640 KB Output is correct
20 Correct 15 ms 640 KB Output is correct
21 Correct 14 ms 640 KB Output is correct
22 Correct 164 ms 640 KB Output is correct
23 Correct 163 ms 640 KB Output is correct
24 Correct 165 ms 640 KB Output is correct
25 Correct 164 ms 640 KB Output is correct
26 Correct 194 ms 640 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 18620 KB Output is correct
2 Correct 653 ms 18560 KB Output is correct
3 Correct 731 ms 18280 KB Output is correct
4 Correct 648 ms 18916 KB Output is correct
5 Execution timed out 3070 ms 14456 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Execution timed out 3055 ms 6292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3033 ms 17656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 14 ms 640 KB Output is correct
20 Correct 15 ms 640 KB Output is correct
21 Correct 14 ms 640 KB Output is correct
22 Correct 164 ms 640 KB Output is correct
23 Correct 163 ms 640 KB Output is correct
24 Correct 165 ms 640 KB Output is correct
25 Correct 164 ms 640 KB Output is correct
26 Correct 194 ms 640 KB Output is correct
27 Correct 30 ms 1016 KB Output is correct
28 Correct 28 ms 1024 KB Output is correct
29 Correct 28 ms 1024 KB Output is correct
30 Correct 685 ms 1016 KB Output is correct
31 Correct 723 ms 1016 KB Output is correct
32 Correct 684 ms 1016 KB Output is correct
33 Correct 278 ms 7144 KB Output is correct
34 Correct 282 ms 7288 KB Output is correct
35 Correct 278 ms 6984 KB Output is correct
36 Execution timed out 3089 ms 6008 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 14 ms 640 KB Output is correct
20 Correct 15 ms 640 KB Output is correct
21 Correct 14 ms 640 KB Output is correct
22 Correct 164 ms 640 KB Output is correct
23 Correct 163 ms 640 KB Output is correct
24 Correct 165 ms 640 KB Output is correct
25 Correct 164 ms 640 KB Output is correct
26 Correct 194 ms 640 KB Output is correct
27 Correct 643 ms 18620 KB Output is correct
28 Correct 653 ms 18560 KB Output is correct
29 Correct 731 ms 18280 KB Output is correct
30 Correct 648 ms 18916 KB Output is correct
31 Execution timed out 3070 ms 14456 KB Time limit exceeded
32 Halted 0 ms 0 KB -