Codeforces Round 914 (Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$ из $$$n$$$ целых положительных чисел и счет. Если ваш счет больше или равен $$$a_i$$$, то вы можете увеличить свой счет на $$$a_i$$$ и удалить $$$a_i$$$ из массива.
Для каждого индекса $$$i$$$ выведите максимальное количество дополнительных элементов массива, которые вы можете удалить, если удалите $$$a_i$$$ и начнёте со счетом, равным $$$a_i$$$. Обратите внимание, что удаление $$$a_i$$$ не должно учитываться в ответе.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел, $$$i$$$-е из которых обозначает максимальное количество дополнительных элементов массива, которые можно удалить, если удалить из массива $$$a_i$$$ и начать со счетом $$$a_i$$$.
4520 5 1 4 231434 7 1442115999999999 999999999 999999999 1000000000 1000000000
4 3 0 3 1 1 0 2 0 4 4 4 4 4
В первом наборе входных данных ответы выглядят следующим образом:
Если мы начинаем с $$$i=4$$$, то наш изначальный счет равен $$$a_4=4$$$ и $$$a=[20,5,1,2]$$$. Мы можем удалить $$$3$$$ дополнительных элемента в следующем порядке:
Если мы начнем с $$$i=1$$$, то сможем удалить все оставшиеся элементы массива, поэтому ответ будет $$$4$$$.
Если мы начнем с $$$i=2$$$, то сможем удалить $$$3$$$ дополнительных элемента в следующем порядке: $$$1$$$, $$$4$$$, $$$2$$$.
Если мы начнем с $$$i=3$$$, то не сможем удалить ни одного дополнительного элемента.
Если мы начинаем с $$$i=5$$$, то можем удалить $$$1$$$ дополнительный элемент: $$$1$$$.
Название |
---|