"Гражданская оборона" - задание на python

Поправил ваш код - нашёл ошибку, заменил несколько однобуквенных имён переменных на говорящие. Строчки в которых были ошибки закомментированы.

Также частично сократил лишние действия, например

1. Заменил

   for i in range(n):
       if villages[i]...
   

   на

   for village in villages:
       if village
   

2. Переместил печать ответа в основной цикл, так как это больше подходит здесь, ведь в вашем решении, в отличии от рабочего примера, не используется функция:

       print(answer, end=' ')
   print()
   

Исправленное решение

n = int(input())
villages = list(map(int, input().split()))

m = int(input())
shelter_range = input().split()

shelters = []
for i in range(m):
    shelters.append((int(shelter_range[i]), i + 1))
shelters.sort()

for village in villages:
    if village > shelters[-1][0]:
        answer = shelters[-1][1]
    elif village < shelters[0][0]:
        answer = shelters[0][1]
    else:
        low = 0
        high = len(shelters) - 1
        while high - low > 1:
            mid = (low + high) >> 1
            if village > shelters[mid][0]:
                low = mid
            else:
                high = mid

        if village - shelters[low][0] < shelters[high][0] - village:
            #answer = low
            answer = shelters[low][1]
        else:
            #answer = high
            answer = shelters[high][1]

    print(answer, end=' ')
print()

Пара моих решений.

Интересно, какое работает быстрее. По асимптотике бинарный поиск должен работать быстрее, ведь в первом решении две сортировки против одной в бинарном поиске, однако обе выполняются встроенной функцией, а бинарный поиск делается виртуальной машиной.

1. Последовательный поиск

Сортируются оба исходных списка (поселения, бомбоубежища), затем поселения раскладываются в соответствии с вынимаемыми по очереди бомбоубежищами. Берём самое близкое бомбоубежище, смотрим какие туда идут поселения, начиная с самого близкого, если дошли до поселения выходящего за пределы данного бомбоубежища, переходим к следующему бомбоубежищу и т. д.

def get_input():
    num = int(input())
    lst = list(map(int, input().split()))
    return num, lst, sorted(lst)

village_num, village_lst, sorted_village_lst = get_input()
shelter_num, shelter_lst, sorted_shelter_lst = get_input()

result = {}
# float('-inf'), float('inf') - отрицательная и положительная бесконечность.
# Использую, чтобы не делать проверку начала и конца списка
sorted_shelter_lst = [float('-inf'), *sorted_shelter_lst, float('inf')]
shelter_indexes = {shltr_name : shltr_idx for shltr_idx, shltr_name in enumerate(shelter_lst, 1)}

cnt = 0
for left, right in zip(sorted_shelter_lst, sorted_shelter_lst[1:]):

    while cnt < len(sorted_village_lst):
        village = sorted_village_lst[cnt]
        if village <= left:
            result[village] = shelter_indexes[left]
        elif village < (left + right) / 2:
            result[village] = shelter_indexes[left]
        else:
            break

        cnt += 1
# Для ответа нужен исходный порядок поселений, который хранится в village_lst.
print(' '.join(str(result[village]) for village in village_lst))

2. Бинарный поиск

Похоже на ваше, но есть отличия. Например, храню исходные индексы бомбоубежищ в словаре.

def get_input():
    num = int(input())
    lst = list(map(int, input().split()))
    return num, lst 

def bin_search(village, shelters):
    left = 0 
    right = len(shelters) - 1 
    while right - left > 1:
        middle = (left + right) // 2        
        if village > shelters[middle]:
            left = middle
        else:
            right = middle

    shelter_idx = right if village > (shelters[left] + shelters[right]) // 2 else left
    return shelters[shelter_idx] 

village_num, village_lst = get_input()
shelter_num, shelter_lst = get_input()
sorted_shelter_lst = sorted(shelter_lst)
original_shelter_indexes = {shltr_name : shltr_idx for shltr_idx, shltr_name in enumerate(shelter_lst, 1)} 

for village in village_lst:
    shltr_name = bin_search(village, sorted_shelter_lst)
    print(original_shelter_indexes[shltr_name], end=' ')
print()