oj.uz

Submission #672905

# Submission time Handle Problem Language Result Execution time Memory
672905 2022-12-18T23:49:31 Z Hello1234 Balloons (CEOI11_bal) Python 3
100 / 100
 1309 ms 23224 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4052 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4068 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4128 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4276 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5872 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 8988 KB 50000 numbers
2 Correct 342 ms 9092 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 13548 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 14904 KB 115362 numbers
2 Correct 784 ms 15792 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 18320 KB 154271 numbers
2 Correct 1309 ms 23196 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1285 ms 21324 KB 200000 numbers
2 Correct 1285 ms 23224 KB 199945 numbers