Zadanie Promień

Question

 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.

Przykład dla wejścia:                         Poprawną odpowiedzią  jest:

6                                                         2 0 1 2 3 -1

2 3 1 4 2 1

6 3 8 8 10 14

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?

Answer 1

Najłatwiej to zrobić robiąc binary search po długości promienia. Jeżeli sprawdzamy czy dla promienia x istnieje rozwiązanie po prostu liczymy l_index i r_index na podstawie wartości x i sprawdźmy sumami prefiksowymi czy suma na przedziale [l_index, r_index] jest większa równa zadanej wartości.

def binary(pref, index, key):
	l, r = 0, max(len(pref)-2-index, index)
	res = -1
	
	while l <= r:
		mid = (l+r)//2
		l_index, r_index = max(0, index-mid), min(len(pref)-2, index+mid)
		
		if pref[r_index+1]-pref[l_index] >= key:
			r = mid-1
			res = mid
		else:
			l = mid+1
			
	return res

Taka implementacja pozbywa się całego bałaganu związanego z aktualizowaniem l_index i r_indeks, na który cierpiał Twój kod