A. Ближайший ноль(мое, медленное).py

"""
Задача № 1.
A. Ближайший ноль
№ Посылки в Яндекс Контесте: # TODO: Вставить номер.
"""
import random
import time


def indexes_of_zeros(enumerated_array):
    """Индексы нулей."""
    return [index for index, value in enumerated_array if value == 0]


def nearest_zero(index, zero_indexes):
    """Поиск ближайшего значения бинарным поиском"""
    left = 0
    right = len(zero_indexes) - 1

    while left <= right:
        mid = (left + right) // 2
        if zero_indexes[mid] == index:
            return 0
        elif zero_indexes[mid] < index:
            left = mid + 1
        else:
            right = mid - 1

    if right < 0:
        return zero_indexes[left] - index
    elif left >= len(zero_indexes):
        return index - zero_indexes[right]
    else:
        return min(zero_indexes[left] - index, index - zero_indexes[right])


def distance(enumerated_array, zero_indexes):
    """Расстояние до ближайшего 0"""
    total_time = 0
    result = []
    for index, value in enumerated_array:
        if value == 0:
            result.append(value)
        elif value != 0:
            start_time = time.time()

            result.append(nearest_zero(index, zero_indexes))

            end_time = time.time()
            elapsed_time = end_time - start_time
            total_time += elapsed_time
    print('find_index time:', total_time)
    return result


def main(array):
    start_time = time.time()
    time_enumerated_array = time.time()
    enumerated_array = list(enumerate(array))
    time_end_enumerated_array = time.time()

    time_zero = time.time()
    zero_indexes = indexes_of_zeros(enumerated_array)
    time_end_zero = time.time()

    time_dis = time.time()
    # TODO: эта функция тратит 99% времени.
    dis = distance(enumerated_array, sorted(zero_indexes))
    time_end_dis = time.time()

    end_time = time.time()
    print(' '.join((map(str, dis))), end='')
    print()
    print('enumerate time:', time_end_enumerated_array - time_enumerated_array)
    print('zero indexes time:', time_end_zero - time_zero)
    print('dis time:', time_end_dis - time_dis)
    print('Всего времени:', end_time - start_time)


# amount=int(input()
# main(list(map(int, input().split())))

# if __name__ == '__main__':
    # main(5, [0, 1, 4, 9, 0])
    # main(6, [0, 7, 9, 4, 8, 20])
    # main(9, [98, 0, 10, 77, 0, 59, 28, 0, 94])

    # генерируем случайный список:
    # random_digits = [random.randint(0, 1000000) for _ in range(1000000)]
    # main(1, random_digits)