oj.uz

Submission #623045

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

EPS = 0.0001

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 13 ms 2900 KB Output is correct
2 Correct 14 ms 2956 KB Output is correct
3 Correct 13 ms 2960 KB Output is correct
4 Correct 16 ms 2840 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2880 KB Output is correct
2 Correct 15 ms 2892 KB Output is correct
3 Correct 18 ms 2980 KB Output is correct
4 Correct 18 ms 2900 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3284 KB Output is correct
2 Correct 92 ms 3664 KB Output is correct
3 Correct 40 ms 3232 KB Output is correct
4 Correct 130 ms 3652 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4044 KB Output is correct
2 Correct 245 ms 4512 KB Output is correct
3 Correct 162 ms 3980 KB Output is correct
4 Correct 128 ms 3968 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 3932 KB Output is correct
2 Correct 248 ms 4508 KB Output is correct
3 Correct 165 ms 3980 KB Output is correct
4 Correct 118 ms 3992 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 4244 KB Output is correct
2 Correct 258 ms 4508 KB Output is correct
3 Correct 150 ms 4044 KB Output is correct
4 Correct 128 ms 3956 KB Output is correct
5 Correct 85 ms 3780 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 23744 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 1088 ms 18772 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 1088 ms 24652 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 1092 ms 30852 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 1080 ms 30792 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 1094 ms 57996 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 1071 ms 68184 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 1079 ms 54480 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 1096 ms 71168 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 1092 ms 56080 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 1094 ms 68472 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 1083 ms 56804 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 1096 ms 67388 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 1080 ms 52848 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 1095 ms 71280 KB Time limit exceeded
2 Halted 0 ms 0 KB -