oj.uz

Submission #623041

# Submission time Handle Problem Language Result Execution time Memory
623041 2022-08-05T06:21:27 Z 54skyxenon Mobile (BOI12_mobile) Python 3
25 / 100
 1000 ms 77748 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 = []

        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([(0, 0)] + intervals + [(l, l)])
        
        for i in range(len(intervals) - 1):
            midpt = (intervals[i][1] + intervals[i + 1][0]) / 2
            if 0 <= midpt <= l:
                return True

        return False

    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 14 ms 3028 KB Output is correct
2 Correct 14 ms 2900 KB Output is correct
3 Correct 20 ms 2932 KB Output is correct
4 Correct 14 ms 2964 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2864 KB Output is correct
2 Correct 16 ms 2932 KB Output is correct
3 Correct 22 ms 2924 KB Output is correct
4 Correct 22 ms 2992 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3416 KB Output is correct
2 Correct 104 ms 3748 KB Output is correct
3 Correct 57 ms 3236 KB Output is correct
4 Correct 139 ms 3708 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4016 KB Output is correct
2 Correct 297 ms 4700 KB Output is correct
3 Correct 156 ms 4048 KB Output is correct
4 Correct 117 ms 4084 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4052 KB Output is correct
2 Correct 277 ms 4640 KB Output is correct
3 Correct 156 ms 4096 KB Output is correct
4 Correct 119 ms 4080 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 4404 KB Output is correct
2 Correct 262 ms 4656 KB Output is correct
3 Correct 163 ms 4172 KB Output is correct
4 Correct 144 ms 4096 KB Output is correct
5 Correct 96 ms 3876 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 25764 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 19892 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 1060 ms 26684 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 1083 ms 33900 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 1089 ms 34080 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 1088 ms 71776 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 77748 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 1097 ms 62232 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 1051 ms 73248 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 1076 ms 56036 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 1057 ms 74096 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 1089 ms 54884 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 1090 ms 67972 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 1068 ms 53196 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 1051 ms 71968 KB Time limit exceeded
2 Halted 0 ms 0 KB -