Mam takie zadanie:
Mamy daną tablicę n liczb całkowitych. Dla każdego elementu tej tablicy szukamy minimalnego promienia ri, takiego że suma wszystkich elementów oddalonych o maksymalnie ri od tego elementu jest równa lub większa od pewnej ustalonej wartości wi.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 <= n <= 500 000) oznaczającą liczbę elementów tablicy. W drugim wierszu wejścia jest n liczb całkowitych t0, t1, . . . , tn−1 (1 ¬<=ti <=1 000 000), gdzie ti oznacza wartość i-tego elementu tablicy, a w trzecim n liczb całkowitych w0, w1, . . . , wn−1 (1 <= wi <= 109 ), gdzie wi oznacza ustaloną wartość dla i-tego elementu tablicy.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać n liczb całkowitych r0, r1, . . . , rn−1, gdzie ri jest minimalnym promieniem dla i-tego elementu, lub wartość −1, gdy nie można znaleźć odpowiedniego promienia.
Próbowałem już różne warianty wyszukiwania binarnego, za każdym razem błędnie, nie mam pomysłu jak dobrze zaimplementować wyszukiwanie binarne w tym zadaniu, ostatni pomysł jaki zrobiłem to:
def binary(pref, index, key):
l_index = index // 2
r_index = (((len(pref) - 2) - index) // 2) + index
za_duzo = True
if pref[r_index+1] - pref[l_index] == key:
return max(index - l_index, r_index - index)
elif pref[r_index+1] - pref[l_index] < key:
za_duzo = False
while index >= l_index > 0 or index <= r_index < len(pref) - 2:
promien = pref[r_index+1] - pref[l_index]
if promien <= key:
if za_duzo is True:
break
if index >= l_index > 0:
l_index -= 1
if index < r_index <= len(pref) - 2:
r_index += 1
else:
if za_duzo is False:
break
if index > l_index >= 0:
l_index += 1
if index <= r_index < len(pref) - 2:
r_index -= 1
if pref[r_index+1] - pref[l_index] >= key:
return max(index - l_index, r_index - index)
return -1
def main():
n = int(input())
t = list(map(int, input().split()))
w = list(map(int, input().split()))
pref = [0]
for num in t:
pref.append(num + pref[-1])
for i in range(len(w)):
print(binary(pref, i, w[i]))
main()
Próbowałem też 4 zmiennymi l_front, h_front, l_back, h_back niestety z miernym skutkiem, czy mógłby mi ktoś pomóc rozwiązać to zadanie?