Submission #672905

#	Time	Username	Problem	Language	Result	Execution time	Memory
672905		Hello1234	Balloons (CEOI11_bal)	Cpython 3	100 / 100	1309 ms	23224 KiB

bal

import sys
from typing import List
# sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline


class Balloon:
    __slots__ = ['x', 'max_radius', 'curr_radius']

    def __init__(self, x: int, max_radius: int, curr_radius: float = float('inf')) -> None:
        self.x = x
        self.max_radius = max_radius
        self.curr_radius = curr_radius


def find_max_radius(b1: Balloon, b2: Balloon):
    # b1 is the already inflated balloon, b2 is the one we want to find
    return ((b1.x - b2.x) ** 2) / (4 * b1.curr_radius)


stack: List[Balloon] = []
radii: List[int] = []

n = int(input())
for _ in range(n):
    x, r = map(int, input().split())
    new_balloon = Balloon(x, r)

    # find max_radius
    # if max_radius > b3.max_radius:
    #   if b3.max_radius > b2.curr_radius:
    #       pop, continue with loop
    #   else:
    #       set balloon radius to min(b3.curr, b3.max, max_radius)
    # else
    #   set b.curr_radius to radius, continue with loop

    # find max_radius
    # if max_radius > b2.curr_radius:
    #   pop, set radius to min, continue with loop
    # if max_radius > b3.max_radius: -> means it
    #   set radius to min(max_radius, curr), continue with

    while stack:
        new_balloon_radius = find_max_radius(stack[-1], new_balloon)
        # print(new_balloon_radius)
        new_balloon.curr_radius = min(new_balloon.curr_radius,
                                      new_balloon.max_radius, new_balloon_radius)
        if new_balloon.curr_radius >= stack[-1].curr_radius:
            stack.pop()
            continue
        else:
            break
    new_balloon.curr_radius = min(new_balloon.curr_radius, new_balloon.max_radius)
    stack.append(new_balloon)
    radii.append(new_balloon.curr_radius)

print(*radii, sep='\n')

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10