|
|
back to boardWhy? 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 |
|
|