Submission #954003

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954003	2024-03-27T05:16:48 Z	ayeshz	Circle selection (APIO18_circle_selection)	Python 3	0 / 100	3000 ms	80772 KB

circle_selection

# 11:10 -> 11:33
import math

n = int(input())
circles = []
for _ in range(n):
    x, y, r = [int(a) for a in input().split()]
    circles.append([x,y,r]) # r=-1 will indicate that the circle is removed
    

n_removed = 0
removing_list = [-1]*n
while n_removed < n:
    r_max = 0
    r_max_idx = -1
    for i in range(len(circles)):
        circle = circles[i]
        if circle[2] > r_max:
            r_max = circle[2]
            r_max_idx  = i
    if r_max_idx == -1:
        break
    x_max = circles[r_max_idx][0]
    y_max = circles[r_max_idx][1]
    r_max = circles[r_max_idx][2]
    
    for i in range(len(circles)):
        circle = circles[i]
        if circle[2] < 1:
            continue
        dis = (circle[0] - x_max)**2 + (circle[1] - y_max)**2
        if dis <= (r_max+circle[2])**2:
            removing_list[i] = str(r_max_idx + 1)
            circle[2] = -1
            n_removed += 1
            
    #n_removed += 1
    circles[r_max_idx][2] = -1
    
print(' '.join(removing_list))

Subtask #1

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	2864 KB	Output is correct
2	Correct	11 ms	2908 KB	Output is correct
3	Correct	10 ms	2908 KB	Output is correct
4	Correct	13 ms	3300 KB	Output is correct
5	Correct	10 ms	2824 KB	Output is correct
6	Correct	11 ms	2908 KB	Output is correct
7	Correct	11 ms	2908 KB	Output is correct
8	Correct	11 ms	2908 KB	Output is correct
9	Correct	11 ms	2908 KB	Output is correct
10	Correct	11 ms	2908 KB	Output is correct
11	Correct	18 ms	3068 KB	Output is correct
12	Correct	17 ms	3060 KB	Output is correct
13	Correct	18 ms	3068 KB	Output is correct
14	Correct	18 ms	2908 KB	Output is correct
15	Correct	19 ms	2908 KB	Output is correct
16	Correct	15 ms	3164 KB	Output is correct
17	Correct	15 ms	3180 KB	Output is correct
18	Correct	15 ms	3164 KB	Output is correct
19	Correct	29 ms	4444 KB	Output is correct
20	Correct	29 ms	4436 KB	Output is correct
21	Correct	39 ms	4188 KB	Output is correct
22	Execution timed out	3080 ms	4072 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1260 ms	80772 KB	Output is correct
2	Correct	1394 ms	80704 KB	Output is correct
3	Correct	1284 ms	80476 KB	Output is correct
4	Correct	1251 ms	80652 KB	Output is correct
5	Execution timed out	3045 ms	46176 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	2908 KB	Output is correct
2	Execution timed out	3043 ms	23608 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	3039 ms	65108 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	2864 KB	Output is correct
2	Correct	11 ms	2908 KB	Output is correct
3	Correct	10 ms	2908 KB	Output is correct
4	Correct	13 ms	3300 KB	Output is correct
5	Correct	10 ms	2824 KB	Output is correct
6	Correct	11 ms	2908 KB	Output is correct
7	Correct	11 ms	2908 KB	Output is correct
8	Correct	11 ms	2908 KB	Output is correct
9	Correct	11 ms	2908 KB	Output is correct
10	Correct	11 ms	2908 KB	Output is correct
11	Correct	18 ms	3068 KB	Output is correct
12	Correct	17 ms	3060 KB	Output is correct
13	Correct	18 ms	3068 KB	Output is correct
14	Correct	18 ms	2908 KB	Output is correct
15	Correct	19 ms	2908 KB	Output is correct
16	Correct	15 ms	3164 KB	Output is correct
17	Correct	15 ms	3180 KB	Output is correct
18	Correct	15 ms	3164 KB	Output is correct
19	Correct	29 ms	4444 KB	Output is correct
20	Correct	29 ms	4436 KB	Output is correct
21	Correct	39 ms	4188 KB	Output is correct
22	Execution timed out	3080 ms	4072 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	2864 KB	Output is correct
2	Correct	11 ms	2908 KB	Output is correct
3	Correct	10 ms	2908 KB	Output is correct
4	Correct	13 ms	3300 KB	Output is correct
5	Correct	10 ms	2824 KB	Output is correct
6	Correct	11 ms	2908 KB	Output is correct
7	Correct	11 ms	2908 KB	Output is correct
8	Correct	11 ms	2908 KB	Output is correct
9	Correct	11 ms	2908 KB	Output is correct
10	Correct	11 ms	2908 KB	Output is correct
11	Correct	18 ms	3068 KB	Output is correct
12	Correct	17 ms	3060 KB	Output is correct
13	Correct	18 ms	3068 KB	Output is correct
14	Correct	18 ms	2908 KB	Output is correct
15	Correct	19 ms	2908 KB	Output is correct
16	Correct	15 ms	3164 KB	Output is correct
17	Correct	15 ms	3180 KB	Output is correct
18	Correct	15 ms	3164 KB	Output is correct
19	Correct	29 ms	4444 KB	Output is correct
20	Correct	29 ms	4436 KB	Output is correct
21	Correct	39 ms	4188 KB	Output is correct
22	Execution timed out	3080 ms	4072 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-