Submission #954001

#	Time	Username	Problem	Language	Result	Execution time	Memory
954001		ayeshz	Circle selection (APIO18_circle_selection)	Pypy 3	7 / 100	3060 ms	104256 KiB

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: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13