oj.uz

Submission #623044

# Submission time Handle Problem Language Result Execution time Memory
623044 2022-08-05T06:23:51 Z 54skyxenon Mobile (BOI12_mobile) Python 3
25 / 100
 1000 ms 72728 KB 
# https://oj.uz/problem/view/BOI12_mobile

EPS = 0.00001

n, l = map(int, input().split())

def dist(c1, c2):
    return ((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2) ** 0.5

coordinates = []
for _ in range(n):
    x, y = map(int, input().split())
    coordinates.append((x, y))

def merge(intervals):
    new_intervals = []
    
    for start, end in sorted(intervals):
        if not new_intervals or new_intervals[-1][1] < start:
            new_intervals.append([start, end])
        else:
            new_intervals[-1][1] = max(new_intervals[-1][1], end)
    
    return new_intervals

def bs(lo, hi):
    def ok(radius):
        intervals = [(0, 0), (l, l)]

        for x1, y1 in coordinates:
            term = (radius ** 2) - (y1 ** 2)
            if term >= 0:
                term_sqrt = term ** 0.5
                intervals.append((x1 - term_sqrt, x1 + term_sqrt))
        
        intervals = merge(intervals)
        m = len(intervals) - 1

        return any(0 <= (intervals[i][1] + intervals[i + 1][0]) / 2 <= l for i in range(m))

    while lo + EPS < hi:
        mid = (lo + hi) / 2

        if not ok(mid):
            hi = mid
        else:
            lo = mid

    return lo

print(bs(0, l))

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2900 KB Output is correct
2 Correct 17 ms 2884 KB Output is correct
3 Correct 13 ms 2900 KB Output is correct
4 Correct 14 ms 2900 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2904 KB Output is correct
2 Correct 18 ms 2900 KB Output is correct
3 Correct 20 ms 2972 KB Output is correct
4 Correct 18 ms 2928 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3396 KB Output is correct
2 Correct 98 ms 3664 KB Output is correct
3 Correct 41 ms 3240 KB Output is correct
4 Correct 141 ms 3572 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3916 KB Output is correct
2 Correct 281 ms 4504 KB Output is correct
3 Correct 159 ms 3916 KB Output is correct
4 Correct 121 ms 3916 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 3904 KB Output is correct
2 Correct 252 ms 4500 KB Output is correct
3 Correct 165 ms 3992 KB Output is correct
4 Correct 124 ms 3960 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 4244 KB Output is correct
2 Correct 252 ms 4504 KB Output is correct
3 Correct 163 ms 4056 KB Output is correct
4 Correct 123 ms 3916 KB Output is correct
5 Correct 87 ms 3916 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 23884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 18816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 24668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 31028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 30880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 58216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 69712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 56484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 70644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 57380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 70420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 56276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 71920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 56460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 72728 KB Time limit exceeded
2 Halted 0 ms 0 KB -