Задача B. WALL-E и кубики

Помогите очень прошу!!)
Задача B. WALL-E и кубики

Робот WALL-E пытается упорядочить груду кубиков. В зоне его ответственности есть nn расположенных друг за другом столбиков, каждый состоит из кубиков, стоящих друг на друге (в ii-м столбике содержится h_ih
i
​
кубиков, столбики нумеруются слева направо). Робот действует по следующему алгоритму: он ищет самый левый столбик с номером ii, в котором кубиков больше, чем в предыдущем, то есть h_{i-1} < h_ih
i−1
​
<h
i
​
. Далее он берет верхний кубик столбика номер ii и сбрасывает его на столбик номер i-1i−1. Если существует столбик с номером i-2i−2 и в нем теперь меньше чем в i-1i−1-м столбике, то данный кубик перемещается далее на i-2i−2-й столбик. И так до тех пор, пока этот кубик либо не дойдет до верха первого столбика либо не упрется в более высокий столбик слева. Далее эта последовательность операций повторяется до тех пор, пока есть два рядом стоящих столбика таких, что h_{i-1} < h_ih
i−1
​
<h
i
​
. По значениям высот исходных nn столбиков вывести высоты упорядоченных nn столбиков.

Формат входных данных

В первой строке содержатся число NN — количество столбиков. В следующей строке находятся NN чисел h_1, h_2, \ldots, h_Nh
1
​
,h
2
​
,…,h
N
​
через пробел, соответствующие высотам соответствующих столбиков. 1 \leq N \leq 10^5 1≤ N≤10
5
, 1 \leq h_i \leq 2*10^91≤h
i
​
≤2∗10
9
.

Формат выходных данных

Вывести NN чисел через пробел, соответствующих высотам столбиков, после того, как WALL-E закончит работу.

Пояснение к примеру.

Следующая серия иллюстраций показывает, куда и какие кубики попали в процессе упорядочивания столбиков:
1. Стартовая ситуация



2. Упорядочили столбик 3



3. Упорядочили столбик 4



4. Упорядочили столбик 6



5. Упорядочили столбик 8



6. Упорядочили столбик 9



7. Упорядочили столбик 10, итоговое расположение кубиков



Sample Input:

10
2 1 6 8 1 2 1 3 5 4
Sample Output:

5 4 4 4 3 3 3 3 2 2

Миниатюры

     

     

 

0

0 из тест. системы, у меня на некоторых работает

0

atlant_007, и ещё, такой вопрос, а ты 5 решил? если да, то на сколько тестов?

0

0 из тест системы, но это после правок

Добавлено через 18 секунд
из моих иногда проходит

Добавлено через 3 минуты
ой про пятую она на 10 тестов

Добавлено через 18 секунд
0 тестов это про валли

0

Romiusse, слушай а можешь описать алгорит или кинуть исходники буду очень благодарен, а то у меня ток на 13 залетело

0

_co_cy_, 1) Рассмотрим как нам оптимально разложить кубики. Воспользуемся средней суммой. Посчитаем сумму кубиков на некоторлм отрезке, и количество столбцов. Далее средней суммой находим среднюю высоту столбцов на этом отрезке. получим что средняя высота = сумму / кол. столбцов. Допустим будет = 4, а остаток сумма mod кол. столбцов = 2.
Значит на этом отрезке начиная с лева первые 2 столбца равны (4+1), тк остаток 2, а остальные 2 из 4 равны 4. Это будет верно, тк если заметить, то кубики после преобразования будут находится в невозрастающем порядке.
2) Но находить среднюю сумму нужно оптимально, тк если тупо вычислить ср сумму всех кубиков, то подучится неправильный ответ, тк мы не можем из более низких столбиков перевести кубики на более высокий.
Я опишу линейный алгоритм за квадрат, но его можно преобразовать за н лог н с помощью бин поиска, но его долго расписывать. Мой квадрат на 16 заходил.
крч из выше опиманного мы будем проверять для каждого слобца оптимально разложение на префиксе.
Будем идти линейно и расклабывать. Сумму кубиков в столбцах мы будем с права на лево. т.е от данной позиции к началу массива. Ок. Теперь сколько столбцов на нужно посчитать идя в лево? Логично, что из более низких недьзя перекинуть на высокие, тогда идя и считая сумму мы будем проверять, а возможно ли нам поставить кубики на ровне с этим столбиком, хватит ли нам кубиков. Будем идти и считать для данного столбик и проверять хватает ли нам кубиков. Если не хватает, то останавливаемся, считаем ср сумму и пересчитываем массив.
3)Но все столбцы считать не оптимально, поэтому будем считать те, которые выше предыдущего.
Ок, для каждого столбца мы сделали подсчеты, в итоге получился ответ.
Я бы скинул всыой код, но степик не пускает, если знаешь как свои решения посмотреть, то напиши, я скину.

1