Оптимизация по памяти

[Son Of Pain]

Самое простое решение, которое приходит в голову:
1) Храним просто массив из пар (номер стека, значение). На каждую такую запись достаточно 40 бит (т. е. 5 байт) - можем сразу выделить 500 килобайт одним куском.
2) На каждый пуш дописываем к массиву новую запись.
3) На каждый поп ищем, начиная с конца массива, первую запись, у которой номер стека совпадает с искомым; выводим ее значение; помечаем запись как пустую.

Непонятно, правда, успеет ли такое брутфорсное решение вложиться во временной лимит. Если нет - придется запоминать в отдельном массиве информацию об индексах, в которых лежат вершины стеков.

[Poma][a]

Можно не скупиться и взять сразу 600 байт..
Но боюсь, не пройдем..
500к на пуши + 499.999+499.998 + .. + 2 + 1.. = 500к + 500к(500к)/2.. не пройдем..
Вот код..
Он снова падает на 10 тесте из-за той же самой памяти..

uses SysUtils;

procedure GetPush(var t : Word; var v : LongInt; s : string);
var
        f, i : Integer;
begin
    f := Pos(' ', s)+1; i := f;
    while s[i] <> ' ' do
        Inc(i);
    t := StrToInt(Copy(s, f, i-f));

    v := StrToInt(Copy(s, i+1, Length(s)))
end;

var
    n, cnt, i, j, v : LongInt;
    t : word;
    s : string[6+6+12+10];
    a : array[1..100000] of record
                            value : LongInt;
                            st : word
                        end;

begin
    ReadLn(n);
    cnt := 0;
    for i := 1 to n do begin
        ReadLn(s);
        if s[2] = 'U' then begin
            GetPush(t, v, s);
            Inc(cnt);
            a[cnt].value := v;
            a[cnt].st := t
        end
        else begin
            t := StrToInt(Copy(s, Pos(' ', s), Length(s)));
            for j := cnt downto 1 do begin
                if a[j].st = t then begin
                    WriteLn(a[j].value);
                    a[j].st := -1;
                    Break
                end {if}
            end {for j }
        end {else}
    end {for i}
end.

Чтож.. нужно работать 5-ю байтами.. Но как? Разбивать число на байты и уже записывать их? а при сравнении брать нужный нам + несколько бит от другого и работать?

[Son Of Pain]

Подозреваю, что из-за выравнивания сейчас sizeof(a) будет равно 800000 по крайней мере в делфи было бы так.

[Poma][a]

Массив структур выравнивает..
Создал 2 массива по 4 и 2 байта каждый.. Всё равно не прохожу по памяти.. Убрал модуль и использовал стандартный Val.. Память - ОК.. время - снова 10 Переписал Val ручками - 11 тест по времени

Этот вариант отпадает..
И я кажется понял, почему падает вариант с SetLength().. ведь мы сначала выделим память, а затем копируем, а потом уже освободим.. И тогда в этот момент памяти у нас в 2 раза больше.. вот и нашли пропажу..
(Беру свои слова по поводу SetLength'a обратно..)

[Аватар]

Ромаха, используя такое все прошло. 17 бит на индекс-указатель и 30 бит на значение - итого 6 байт, даже один бит лишний

var stacks: array[1..1000] of Longint;
    values: array[1..600000] of Byte;

[Poma][a]

Супер..
А можно чуть-чуть подробнее?
в stacks храним указатели на 1-ый элемент?
values хранят значение и указатель на следующий элемент?

[Аватар]

Ага. Может лучше код вложением, что бы много букв не было?

[Poma][a]

Хотелось бы самому написать.. (можно пару слов об идее, если Вам не в тягость)

[Аватар]

Индексы для values от 1 до 100000 (max 7 бит) - адресуют не каждый байт в массиве, а группу из шести байтов. В первых трех байтах и старших 6 битах 4-го - значение. В последних двух байтах и младшем бите 4-го - индекс на следующий. Те же списки, но чуть хитрей. Данные приходится побайтно засовывать с использованием битовых сдвигов, AND и OR. И читать тоже

[Poma][a]

Огромное спасибо!..
Завтра попытаюсь закодить..