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

[Poma][a]

Добрый Вечер.
Прошу помощи..

Есть задачка : тыц
Она на буржуйском (при необходимости переведу)

Написал код, он валится на 5 тесте Memory limit exceeded

Основная фишка - это динамические массивы и иже с ними..

uses SysUtils;

var
    a : array of 
        record
            nam : Integer;
            st : array of LongInt
        end;

procedure GetPush(var t, v : LongInt; s : string);
var
        f, i : LongInt;
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;

procedure AddElem(t, v : Integer);
var
    i : Integer;
begin
    for i := Low(a) to High(a) do begin
        if a[i].nam = t then begin
            SetLength(a[i].st, High(a[i].st)+2);
            a[i].st[High(a[i].st)] := v;
            Exit
        end
    end;


    SetLength(a, High(a)+2);
    a[High(a)].nam := t;
    SetLength(a[High(a)].st, 1);
    a[High(a)].st[0] := v
end;

procedure PopElem(t : Integer);
var
        i, j : Integer;
begin
    for i := Low(a) to High(a) do begin
        if a[i].nam = t then begin
            WriteLn(a[i].st[High(a[i].st)]);
            SetLength(a[i].st, High(a[i].st));
            Exit
        end
    end
end;

var
    n, i, t, v : LongInt;
    s : string[6+6+12+10];

begin
{   Assign(input, 'input.txt');
    Reset(input);
    Assign(output, 'output.txt');
    Rewrite(output);
 }
    ReadLn(n);

    for i := 1 to n do begin
        ReadLn(s);
        if s[2] = 'U' then begin
            GetPush(t, v, s);
            AddElem(t, v)
        end
        else begin
            t := StrToInt(Copy(s, Pos(' ', s), Length(s)));
            PopElem(t)
        end
    end
end.

Проходить должно.. Но валится.. Прошу помощи..

Мои идеи..
1) Я где-то накосячил с удалением памяти..
2) Наверное, где-то идет копирование массивов(при увеличении длины).. И из-за этого едим много памяти..

Спасибо!

Удачи!)

[Stilet]

А что за задача?
У меня не валится если я по тупому ввожу две цифры через пробел.
Задачу озвучь, ато я на тот сайт выйтить не могу чет.

[Poma][a]

1220. Stacks
Ограничение времени: 0.5 секунды
Ограничение памяти: 0.75 МБ
Ограничение на язык: C, C++, Pascal
Imagine, that you are employed by a software development company. You work now on the famous "D++ project", which is devoted to the creation of a new generation programming language. Your particular task is quite prosaic, though. You are to develop the memory manager being able to work with a large number of stacks.
Исходные данные
The first line of the input contains the total number of stack operations N, 0 < N ≤ 100000. Each of the next N lines contains a description of a stack operation, either in the form PUSH A B (meaning to push B into stack A), or in the form POP A (meaning to pop an element from stack A), where A is the number of stack (1 ≤ A ≤ 1000), and B is an integer (0 ≤ B ≤ 109). You may assume, that every operation is correct (i.e., before each POP operation, the respective stack is not empty).
Результат
For each POP operation, described in the input, output the value, which this POP operation gets from the top of that stack, to which it is applied. Numbers should appear according to the order of the POP operations in the input. Each number should be output in a separate line.
Пример
исходные данные результат

7
PUSH 1 100
PUSH 1 200
PUSH 2 300
PUSH 2 400
POP 2
POP 1
POP 2



400
200
300

Автор задачи: Pavel Atnashev
Источник задачи: The Seventh Ural State University collegiate programming contest

И на компе не должна валиться.. Памяти-то ей в волю..

[Аватар]

Ромаха, по коду без проблема. По памяти видимо из-за динамических массивов - любой SetLength отводит новую память для массива и копирует из старого. Попробуй GetMem и соответственно аккуратненько FreeMem для структуры значений примерно в таком виде

type Prec1 = ^Trec1;
     Trec1 = record
       Value: LongInt;
       Next: Prec1;
     end;

Для номеров стеков аналогичное с номером стека и ссылью на первое значение, вернее на последнее

[Poma][a]

По памяти видимо из-за динамических массивов - любой SetLength отводит новую память для массива и копирует из старого.

Черт.. SetLength() - меня разочаровывает..
Спасибо!

Попробую

[Poma][a]

Уже 10 тест.. Снова по памяти..

type
	pstack = ^stack;
    stack = record
        value : Integer;
        next : pstack;
    end;
    pelem = ^elem;
    elem = record
        nam : Integer;
        next : pelem;
        st : pstack;
    end;

var
    head : ^elem;

function StrToInt(s : string) : Integer;
var
	er : Byte;
	r : Integer;
begin
   Val(s, r,er);
   StrToInt := r
end;
procedure GetPush(var t : Integer; var v : Integer; 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;

procedure AddElem(t, v : Integer);
var
	p, tElem : ^elem;
	temp : ^stack;
begin

	if head = nil then begin
		GetMem(head, SizeOf(elem));
		head^.nam := t;
		head^.next := nil;
		GetMem(head^.st, SizeOf(stack));
		head^.st^.value := v;
		head^.st^.next := nil;
		Exit
	end;

	p := head;
	while p <> nil do begin
		if (p^.nam <> t) then
			p := p^.next
		else begin
			temp := p^.st;
			GetMem(p^.st, SizeOf(stack));
                        p^.st^.value := v;
			p^.st^.next := temp;
			Exit
		end {else (10X Arigato)}
	end; {while p <> nill}

	tElem := head;
	GetMem(head, SizeOf(elem));
	head^.nam := t;
	head^.next := tElem;
	GetMem(head^.st, SizeOf(stack));
	head^.st^.value := v;
	head^.st^.next := nil
end;

procedure PopElem(t : Integer);
var
	p, p1 : ^elem;
	temp : ^stack;
begin
	if head^.nam = t then begin
		temp := head^.st;
		WriteLn(temp^.value);
		head^.st := head^.st^.next;
		FreeMem(temp);
        Exit
	end;

	p1 := head;
    p := head^.next;
	while p <> nil do begin
		if p^.nam <> t then begin
			p1 := p;
			p := p^.next
		end
		else begin
			temp := p^.st;
			WriteLn(temp^.value);
			p^.st := p^.st^.next;
			FreeMem(temp);
			if p = nil then begin
				p1^.next := p^.next;
				FreeMem(p)
			end;
	        Exit
		end {else}
	end {while p <> nil}
end;

var
    n, i, v : Integer;
    t : Integer;
    s : string;
	th : ^elem;
	ps, temp : ^stack;
begin
    ReadLn(n);
    head := nil;

    for i := 1 to n do begin
        ReadLn(s);
        if s[2] = 'U' then begin
            GetPush(t, v, s);
            AddElem(t, v)
        end
        else begin
            t := StrToInt(Copy(s, Pos(' ', s), Length(s)));
            PopElem(t)
        end
    end;

    while head <> nil do begin
        th := head^.next;
        ps := head^.st;
        while ps <> nil do begin
            temp := ps^.next;
            FreeMem(ps);
            ps := temp
        end; {while ps <> nil}
        FreeMem(head);
        head := th
    end {while head <> nil}
end.

[Son Of Pain]

Представь себе худший из возможных кейсов - 100000 пушей в разные стеки.
Лимит памяти - 750 килобайт.
Следовательно, можно использовать 7 байт на одну операцию.
Как ты думаешь, на сколько больше памяти съедят все эти линкедлисты?

[Poma][a]

Как ты думаешь, на сколько больше памяти съедят все эти линкедлисты?

Как минимум 8..
Хорошо.. Идеи?
Динамический массив не прошел, т.к. он каждый раз копирует массив, не убирая память..
Списки тоже..

[Son Of Pain]

Первая "идея" - не выделять новый блок памяти на каждый пуш. Потому что behind the scenes гетмем забирает еще несколько байт для своих внутренних нужд.

[Poma][a]

Хорошо.. Но все равно худший вариант не пройдет..
Нужно как-то отказываться от указателей.. (наверное)..