Тема: Як оптимізувати?
Неможу ніяк оптимізувати код до задачі. Проходить лише 15 тестів на алготестері з 25. Ось умова і код. Допоможіть хто може буду дуже вдячний.
Марiчка i Зеник довго думали, зважували всi “за” i “проти”. Було багато дискусiй, суперечок,
непорозумiнь. Вони не були впевнениi чи готовi до такої вiдповiдальностi. Але, здається, вони
таки зважилися на цей поступок. В сiм’ї нарештi буде поповнення!
В зоомагазинi був дуже широкий вибiр котикiв, на всi смаки. Нiхто не мiг залишитися рiвно-
душним. В молодят аж очi розбiгалися вiд такого рiзноманiття. Марiчка дуже хотiла обрати саме
того єдиного, найкращого, найвеселiшого, найдобрiшого котика. Зеник же був просто щасливий
що в них вдома нарештi появиться котик.
Процес вiдбору виявився доволi складним. Ключовим параметром для Марiчки виявився па-
раметр пухнастостi котикiв. Всi n котикiв в зоомагазинi вишикувалися в ряд. В i-го котика рiвень
пухнастостi рiвний aі. Процес вiдбору був багатоетапний. На кожному етапi Марiчка забракову-
вала деяких котикiв, i вони покидали конкурс. Решта переходили в наступний раунд, не мiняючи
свого вiдносного порядку.
Правила були наступнi: якщо безпосередньо справа вiд якогось котика стояв котик з бiльшим
рiвнем пухнастостi, то на цьому етапi цей котик вважався малопухнастим. В кiнцi кожного етапу
всi малопухнастi котики вибували з конкурсу. Зауважимо, що спочатку вибиралися малопухнастi
котики, а тодi вже всi вони вибували з конкурсу.
В результатi всього цього процесу залишалася деяка послiдовнiсть котикiв, таких що жодного
з них Марiчка не могла назвати малопухнастим. Одного з цих щасливцiв пара i забере до себе
до дому. Ваше завдання визначити результуючу послiдовнiсть немалопухнастих котикiв
Вхiднi данi
В першому рядку задано одне цiле число n кiлькiсть котикiв в зоомагазинi. В наступному
рядку заданi числа ai рiвнi пухнастостi котикiв, в такому порядку як вони вишикувалися.
Гарантується що у всiх котикiв рiвнi пухнастостi рiзнi.
Вихiднi данi
В першому рядку виведiть одне цiле число m кiлькiсть котикiв що залишаться. В насту-
пному рядку виведiть m чисел рiвнi пухнастостi котиків.
Обмеження: 1<=n<=100000, 1<=ai<=1000000000
Приклади:
Вхідні дані: Вихідні дані:
7 2
6 5 7 2 3 1 4 7 4
type
mas = array[1..100000] of int64;
var
n, i, k, l, m, max: int64;
a, b: mas;
begin
readln(n);
for i := 1 to n do
read(a[i]);
l := 1; m := 0;
while l <= n do
begin
max := 0;
for i := l to n do
begin
if max < a[i] then begin max := a[i]; k := i; end; end;
m := m + 1;
b[m] := max;
l := k + 1;
end;
writeln(m);
for i := 1 to m do write(b[i], ' ');
end.