Условие задачи
Кузя был очень удивлён, когда на десятилетие выпуска не приехала большая часть его одноклассников.
«Чему тут удивляться, разъехались по миру», — сказал ему один из пришедших одноклассников.
Кузя решил, что раз одноклассники не приехали на выпускной, то Кузя сам привезёт выпускной им. Правда для этого Кузе необходимо узнать, в какие страны они переехали.
Кузя знает, что каждая страна разрешает переезд на основе двух характеристик:
- Минимальный доход, необходимый для проживания;
- Обязательное наличие высшего образования.
Также Кузя знает, что некоторые страны разрешают переезд непосредственным детям своих граждан без необходимости удовлетворять описанным выше характеристикам.
Про каждого из уехавших одноклассников Кузя выяснил следующую информацию (мы сами не понимаем, где он всё это узнал):
- Величина дохода;
- Наличие высшего образования;
- Гражданство родителей.
Теперь Кузя просит вас, как лучшего игрока в GeoGuesser среди выпускников, выяснить страну, в которую переехал каждый из непришедших на выпускной одноклассников.
Формат ввода
Первая строка содержит одно целое число N (1 ≤ N ≤ 2·105) — количество стран, рассматриваемых для переезда.
Вторая строка содержит N целых чисел через пробел ai (0 ≤ ai ≤ 109) — минимальный доход, необходимый для переезда в i-ю страну.
Третья строка содержит N целых чисел через пробел bi (0 ≤ bi ≤ 1) — bi равно 1, если для переезда в i-ю страну обязательно наличие высшего образования.
Четвертая строка содержит N целых чисел через пробел ci (0 ≤ ci ≤ 1) — ci равно 1, если непосредственные дети граждан i-й страны могут переехать в i-ю страну, не удовлетворяя условиям на доход и высшее образование.
Страны нумеруются с 1 по N в порядке ввода.
Пятая строка содержит одно целое число Q (1 ≤ Q ≤ 2·105) — количество одноклассников, не пришедших на выпускной.
Шестая строка содержит Q целых чисел через пробел xj (0 ≤ xj ≤ 109) — доход j-го одноклассника.
Седьмая строка содержит Q целых чисел через пробел yj (0 ≤ yj ≤ 1) — yj равно 1, если у j-го одноклассника есть высшее образование.
Восьмая строка содержит Q целых чисел через пробел zj (0 ≤ zj ≤ N) — гражданство родителей j-го одноклассника, заданное номером страны или 0, если их гражданство неизвестно.
Одноклассники нумеруются с 1 по Q в порядке ввода.
Формат вывода
В единственной строке выведите Q целых чисел через пробел tj (0 ≤ tj ≤ N) — номер страны, которую выбрал для переезда j-й одноклассник.
Каждый одноклассник может выбрать только страну, в которую он имеет право переехать (согласно условиям).
В случае, если одноклассник может выбрать несколько стран для переезда, он выберет страну с наименьшим номером в списке (Кузя любезно отсортировал страны в порядке убывания привлекательности для переезда).
Если одноклассник не мог переехать ни в одну из описанных стран, выведите 0.
Ссылка на задачу № 2: https://hsto.org/getpro/freelansim/allfiles/16/169/169389/Microsoft_Word_Document___kopiya__1_.pdf
def binary_search(tuples_countrys, fact_cash, n_country):
if n_country == 1:
hold = tuples_countrys[0]
if hold[0] <= fact_cash:
return tuples_countrys
else:
return []
low = 0
high = n_country - 1
search_res = False
guess = tuples_countrys[0]
middle = 0
while low <= high and not search_res:
middle = (low + high) // 2 # отвечает за средний эллемент в массиве
guess = tuples_countrys[middle]
if guess[0] == fact_cash:
search_res = True
elif guess[0] > fact_cash:
high = middle - 1
else:
low = middle + 1
if middle == n - 1 and guess[0] <= fact_cash:
return tuples_countrys
while guess[0] <= fact_cash and middle < n_country - 1:
middle += 1
guess = tuples_countrys[middle]
return tuples_countrys[:middle]
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
q = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
z = list(map(int, input().split()))
j = 0
output_country = [0] * q
tuples_country = []
i = 0
while i < n:
tuples_country.append((a[i], b[i], i + 1))
i += 1
tuples_country.sort()
hold_countrys = []
while j < q:
if c[z[j] - 1] == 1:
output_country[j] = z[j]
hold_countrys.clear()
hold_countrys.extend(binary_search(tuples_country, x[j], n))
if len(hold_countrys) == 0:
j += 1
continue
if y[j] == 1:
hold_countrys.sort(key=lambda a: a[2])
hold = hold_countrys[0]
country = hold[2]
else:
hold_countrys.sort(key=lambda a: a[1])
country = n
hold = hold_countrys[0]
if hold[1] == 1:
j += 1
continue
for guess in hold_countrys:
if guess[1] == 1:
break
if country > guess[2]:
country = guess[2]
if country < output_country[j] or output_country[j] == 0:
output_country[j] = country
j += 1
print(*output_country)
Пример ввода и вывода:
Ввод
2
10 9
1 0
0 1
5
0 0 11 10 9
0 1 0 1 1
2 1 0 0 0
Вывод
2 0 2 1 2
c
, вам достаточно просто проверить там 1 или 0 по конкретному индексу в массиве