ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1037. Memory Management

Why? Memory Limit exceeded! How can that be possible?
Posted by JIM 18 Jul 2004 19:02
  I've met this problem for several times on URAL, and still unsolved yet. Please help me.
  I think that I've only used (30000+30000)*2(for v and sum) + (30000+600)*2(for p and first) + (30000+600)*6(for p^ and first^), that's 364Kb. Plus the stack Pascal established automatically in the progress, each part only use the extra space for log(30000), so totally much less than 1000Kb, but URAL says 'Memory Limit Exceeded!'. Can you help me?

Here is my program:
const
  maxn=30000;
  maxt=600;
type
  p_type=^ptype;
  ptype=record
          n:integer;
          pre,next:p_type;
        end;
var
  v,sum:array[1..maxn] of integer;
  p:array[1..maxn] of p_type;
  first:array[1..maxt] of p_type;
  time0,time,x,i:integer;
  com:char;

procedure build(ID:integer);
  begin
    sum[ID]:=1;
    if ID*2<=maxn then begin
      build(ID*2);
      inc(sum[ID],sum[ID*2]);
    end;
    inc(x); v[ID]:=x;
    if ID*2+1<=maxn then begin
      build(ID*2+1);
      inc(sum[ID],sum[ID*2+1]);
    end;
  end;

procedure insert(ID:integer; x:integer);
  begin
    inc(sum[ID]);
    if x<v[ID] then insert(ID*2,x)
    else if x>v[ID] then insert(ID*2+1,x);
  end;

procedure work;
  var now:p_type;
      i:integer;
  begin
    inc(time0);
    while first[maxt]^.next<>nil do begin
      now:=first[maxt]^.next;
      first[maxt]^.next:=now^.next;
      now^.pre:=nil; now^.next:=nil;
      insert(1,now^.n);
    end;
    for i:=maxt downto 2 do begin
      first[i]^.next:=first[i-1]^.next;
      if first[i]^.next<>nil then
        first[i]^.next^.pre:=first[i];
    end;
    first[1]^.next:=nil;
  end;

procedure search(ID:integer; var ans:integer);
  begin
    dec(sum[ID]);
    if (ID*2<=maxn) and (sum[ID*2]>0) then search(ID*2,ans)
    else if (ID*2+1>maxn) or (sum[ID]=sum[ID*2+1]) then ans:=v[ID]
    else search(ID*2+1,ans);
  end;

begin
  assign(input,'1037.in'); reset(input);
  assign(output,'1037.out'); rewrite(output);
  x:=0; build(1);
  for i:=1 to maxn do begin
    new(p[i]);
    p[i]^.n:=i;
    p[i]^.pre:=nil;
    p[i]^.next:=nil;
  end;
  for i:=1 to maxt do begin
    new(first[i]);
    first[i]^.pre:=nil;
    first[i]^.next:=nil;
  end;

  time0:=0;
  repeat
    read(time);
    while time0<time do work;
    repeat read(com); until com in ['+','.'];
    if com='+' then begin
      readln;
      search(1,x);
      writeln(x);
      p[x]^.next:=first[1]^.next;
      if first[1]^.next<>nil then
        first[1]^.next^.pre:=p[x];
      first[1]^.next:=p[x];
      p[x]^.pre:=first[1];
    end else begin
      readln(x);
      if p[x]^.pre=nil then writeln('-')
      else begin
        writeln('+');
        p[x]^.pre^.next:=p[x]^.next;
        if p[x]^.next<>nil then
          p[x]^.next^.pre:=p[x]^.pre;
        p[x]^.next:=first[1]^.next;
        if first[1]^.next<>nil then
          first[1]^.next^.pre:=p[x];
        first[1]^.next:=p[x];
        p[x]^.pre:=first[1];
      end;
    end;
  until eof(input);
  close(input); close(output);
end.
Re: Why? Memory Limit exceeded! How can that be possible?
Posted by Saturn 19 Jul 2004 11:40
I can solve this problem without using pointer so it need
less memory than yours
I have fixed your program and it got AC in 1.2s 741KB
Post your email here , I will send it to you :)
Re: Why? Memory Limit exceeded! How can that be possible?
Posted by JIM 19 Jul 2004 21:06
Thank you for your advice, and I'll try to change mine myself to get AC. Here is my email:seek_jim20@hotmail.com
Pleased to get a new friend.
Re: Why? Memory Limit exceeded! How can that be possible?
Posted by mkd 19 Jul 2004 22:42
When you allocate memory with new (or malloc IMHO too) it usually consumes more memory than it should.
But if you know how many elements you'll need you can make it better - instead of writing (for example)
int *x = new int;

you can write
int mem[max_elems];
int elems_used = 0;

and later in your code

int *x = &mem[elems_used++];
Re: Why? Memory Limit exceeded! How can that be possible?
Posted by Saturn 19 Jul 2004 23:11
I think it's good idea.
My email is : quangviet2004@yahoo.com