oj.uz

Submission #953667

# Submission time Handle Problem Language Result Execution time Memory
953667 2024-03-26T12:20:44 Z ayeshz Circle selection (APIO18_circle_selection) PyPy 3
7 / 100
 3000 ms 92116 KB 
n = int(input())
def intersect(x1,y1,r1,x2,y2,r2):
    dist = pow(x1-x2,2) + pow(y1-y2,2)
    if dist <= pow(r1 + r2,2):
        return True
    return False
circles = []
for i in range(n):
    temp = tuple(map(int,input().split()))
    circles.append((i+1,temp[0],temp[1],temp[2]))
ais = [-1] * n
circles.sort(key=lambda x: x[3],reverse=True)
for i in range(n):
    if ais[circles[i][0]-1] != -1:
        continue
    x, y, r = circles[i][1],circles[i][2],circles[i][3]
    ais[circles[i][0]-1] = circles[i][0]
    # this is largest circle, find intersecting circles
    for j in range(i+1,n):
        if ais[circles[j][0]-1] != -1:
            continue
        if intersect(x,y,r,circles[j][1],circles[j][2],circles[j][3]):
            ais[circles[j][0]-1] = circles[i][0]
#print(ais)
print(' '.join(map(str,ais)))

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18236 KB Output is correct
2 Correct 28 ms 18236 KB Output is correct
3 Correct 28 ms 18232 KB Output is correct
4 Correct 27 ms 18236 KB Output is correct
5 Correct 28 ms 18272 KB Output is correct
6 Correct 32 ms 18228 KB Output is correct
7 Correct 29 ms 18236 KB Output is correct
8 Correct 29 ms 18236 KB Output is correct
9 Correct 30 ms 18236 KB Output is correct
10 Correct 30 ms 18228 KB Output is correct
11 Correct 36 ms 19000 KB Output is correct
12 Correct 35 ms 19036 KB Output is correct
13 Correct 45 ms 18988 KB Output is correct
14 Correct 46 ms 19156 KB Output is correct
15 Correct 36 ms 19176 KB Output is correct
16 Correct 54 ms 19504 KB Output is correct
17 Correct 54 ms 19232 KB Output is correct
18 Correct 53 ms 19552 KB Output is correct
19 Correct 82 ms 24112 KB Output is correct
20 Correct 80 ms 24116 KB Output is correct
21 Correct 91 ms 25312 KB Output is correct
22 Correct 318 ms 24120 KB Output is correct
23 Correct 330 ms 23856 KB Output is correct
24 Correct 306 ms 23852 KB Output is correct
25 Correct 303 ms 25072 KB Output is correct
26 Correct 310 ms 24108 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 91592 KB Output is correct
2 Correct 1240 ms 92116 KB Output is correct
3 Correct 1175 ms 85444 KB Output is correct
4 Correct 1171 ms 91508 KB Output is correct
5 Execution timed out 3045 ms 80080 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18200 KB Output is correct
2 Execution timed out 3054 ms 39428 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 3031 ms 78308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18236 KB Output is correct
2 Correct 28 ms 18236 KB Output is correct
3 Correct 28 ms 18232 KB Output is correct
4 Correct 27 ms 18236 KB Output is correct
5 Correct 28 ms 18272 KB Output is correct
6 Correct 32 ms 18228 KB Output is correct
7 Correct 29 ms 18236 KB Output is correct
8 Correct 29 ms 18236 KB Output is correct
9 Correct 30 ms 18236 KB Output is correct
10 Correct 30 ms 18228 KB Output is correct
11 Correct 36 ms 19000 KB Output is correct
12 Correct 35 ms 19036 KB Output is correct
13 Correct 45 ms 18988 KB Output is correct
14 Correct 46 ms 19156 KB Output is correct
15 Correct 36 ms 19176 KB Output is correct
16 Correct 54 ms 19504 KB Output is correct
17 Correct 54 ms 19232 KB Output is correct
18 Correct 53 ms 19552 KB Output is correct
19 Correct 82 ms 24112 KB Output is correct
20 Correct 80 ms 24116 KB Output is correct
21 Correct 91 ms 25312 KB Output is correct
22 Correct 318 ms 24120 KB Output is correct
23 Correct 330 ms 23856 KB Output is correct
24 Correct 306 ms 23852 KB Output is correct
25 Correct 303 ms 25072 KB Output is correct
26 Correct 310 ms 24108 KB Output is correct
27 Correct 95 ms 25648 KB Output is correct
28 Correct 117 ms 25136 KB Output is correct
29 Correct 95 ms 25172 KB Output is correct
30 Correct 1232 ms 25988 KB Output is correct
31 Correct 1317 ms 26460 KB Output is correct
32 Correct 1253 ms 25796 KB Output is correct
33 Correct 370 ms 42180 KB Output is correct
34 Correct 380 ms 42432 KB Output is correct
35 Correct 396 ms 43540 KB Output is correct
36 Execution timed out 3047 ms 39520 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18236 KB Output is correct
2 Correct 28 ms 18236 KB Output is correct
3 Correct 28 ms 18232 KB Output is correct
4 Correct 27 ms 18236 KB Output is correct
5 Correct 28 ms 18272 KB Output is correct
6 Correct 32 ms 18228 KB Output is correct
7 Correct 29 ms 18236 KB Output is correct
8 Correct 29 ms 18236 KB Output is correct
9 Correct 30 ms 18236 KB Output is correct
10 Correct 30 ms 18228 KB Output is correct
11 Correct 36 ms 19000 KB Output is correct
12 Correct 35 ms 19036 KB Output is correct
13 Correct 45 ms 18988 KB Output is correct
14 Correct 46 ms 19156 KB Output is correct
15 Correct 36 ms 19176 KB Output is correct
16 Correct 54 ms 19504 KB Output is correct
17 Correct 54 ms 19232 KB Output is correct
18 Correct 53 ms 19552 KB Output is correct
19 Correct 82 ms 24112 KB Output is correct
20 Correct 80 ms 24116 KB Output is correct
21 Correct 91 ms 25312 KB Output is correct
22 Correct 318 ms 24120 KB Output is correct
23 Correct 330 ms 23856 KB Output is correct
24 Correct 306 ms 23852 KB Output is correct
25 Correct 303 ms 25072 KB Output is correct
26 Correct 310 ms 24108 KB Output is correct
27 Correct 1163 ms 91592 KB Output is correct
28 Correct 1240 ms 92116 KB Output is correct
29 Correct 1175 ms 85444 KB Output is correct
30 Correct 1171 ms 91508 KB Output is correct
31 Execution timed out 3045 ms 80080 KB Time limit exceeded
32 Halted 0 ms 0 KB -