1

Тема: Як оптимізувати?

Неможу ніяк оптимізувати код до задачі. Проходить лише 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.

2

Re: Як оптимізувати?

1. Останній завжди потрапляє в список.
2. Якщо йти з кінця, то перший більший за останнього доданого до списку потрапляє в список.
Таким чином, за O(n) можна все зібрати у зворотному порядку.

Подякували: leofun011

3

Re: Як оптимізувати?

Фактично має залишитися спадна послідовність, від найбільшого елемента до останнього. Якщо йти з кінця, то має бути доволі легко усе відібрати. Йти з кінця можна отак:

BCount := 1;
Max := a[n];
b[BCount] := Max;
for i := n - 1 downto 1 do 
  //...
Подякували: leofun011

4

Re: Як оптимізувати?

Дякую за ідею пане Koala. Пішли всі тести. Ось код:

type
  mas = array[1..100000] of int64;

var
  n, i, m: int64; 
  a, b: mas;

begin
  readln(n);
  for i := 1 to n do 
    read(a[i]);
  
  m := 1; b[m] := a[n];  
  for i := n - 1 downto 1 do
    if b[m] < a[i] then begin m := m + 1; b[m] := a[i]; end;
  writeln(m);
  for i := m downto 1 do write(b[i], ' ');
  
end.