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

I've got WA on test 2 a lot of times :-( Help me please!
Posted by hey, dude! 24 Mar 2005 19:53
 I make two heaps - "used" for blocks, which are allocated at this moment; "free" - for free blocks.
 First element of "used" is block whith minimum time.
 First element of "free" is block whith minimum ID.
 At each step I refresh this heaps in such way : I look at the used[1] and if its time < time of request - 599 then I delete it from "used" and insert it to "free". And I do this operation until used[1].t >= time of request - 599.

This is my code :

const
 max = 30000;
 del = 600;
type
 long = record n,t : word; end;
var
 free : array [1..max] of word;
 used : array [1..max] of long;
 pf,pu : array [1..max] of word;
 i,lf,lu,time,num : word;
 c : char;
procedure inpt;
begin
 fillchar(used,sizeof(used),0);
 fillchar(pu,sizeof(pu),0); lu := 0;
 for i := 1 to max do
 begin
  free[i] := i;
  pf[i] := i;
 end;
 lf := max;
end;
procedure up_f(x : word);
var
 l,c : word;
begin
 if (x div 2 > 0) and (free[x div 2] > free[x])
 then l := x div 2 else l := x;
 if (l <> x) then
 begin
  c := free[x]; free[x] := free[l]; free[l] := c;
  pf[free[x]] := x; pf[free[l]] := l;
  up_f(l);
 end;
end;
procedure dn_f(x : word);
var
 l,c : word;
begin
 if (2*x <= lf) and (free[x] > free[2*x]) then l := 2*x else l := x;
 if (2*x+1 <= lf) and (free[l] > free[2*x+1]) then l := 2*x+1;
 if (l <> x) then
 begin
  c := free[x]; free[x] := free[l]; free[l] := c;
  pf[free[x]] := x; pf[free[l]] := l;
  dn_f(l);
 end;
end;
procedure up_u(x : word);
var
 l : word;
 c : long;
begin
 if (x div 2 > 0) and (used[x div 2].t > used[x].t)
 then l := x div 2 else l := x;
 if (l <> x) then
 begin
  c := used[x]; used[x] := used[l]; used[l] := c;
  pu[used[x].n] := x; pu[used[l].n] := l;
  up_u(l);
 end;
end;
procedure dn_u(x : word);
var
 l : word;
 c : long;
begin
 if (2*x <= lu) and (used[x].t > used[2*x].t) then l := 2*x else l := x;
 if (2*x+1 <= lu) and (used[l].t > used[2*x+1].t) then l := 2*x+1;
 if (l <> x) then
 begin
  c := used[x]; used[x] := used[l]; used[l] := c;
  pu[used[x].n] := x; pu[used[l].n] := l;
  dn_u(l);
 end;
end;
procedure delfree;
begin
 pf[free[1]] := 0;
 free[1] := free[lf]; dec(lf);
 pf[free[1]] := 1;
 dn_f(1);
end;
procedure insfree(n : word);
begin
 inc(lf); free[lf] := n; pf[n] := lf;
 up_f(lf);
end;
procedure delused;
begin
 pu[used[1].n] := 0;
 used[1] := used[lu]; dec(lu);
 pu[used[1].n] := 1;
 dn_u(1);
end;
procedure insused(n,t : word);
begin
 inc(lu); used[lu].n := n; used[lu].t := t;
 pu[n] := lu; up_u(lu);
end;
procedure refresh;
begin
 while (lu > 0) and (time - used[1].t >= del) do
 begin
  insfree(used[1].n);
  delused;
 end;
end;
procedure find;
begin
 while not(eof) do
 begin
  read(time); refresh;
  c := ' '; while (c = ' ') do read(c);
  case c of
   '+' :
   begin
    writeln(free[1]);
    insused(free[1],time);
    delfree;
   end;
   '.' :
   begin
    read(num);
    if (pu[num] = 0) then writeln('-')
    else
    begin
     writeln('+');
     used[pu[num]].t := time;
     dn_u(pu[num]);
    end;
   end;
  end;
  readln;
 end;
end;
begin
 inpt;
 find;
end.

Could you give me a test on which my code will give wrong answer? Thanks a lot!
Re: I've got WA on test 2 a lot of times :-( Help me please!
Posted by Cybernetics Team 24 Mar 2005 20:07
Here is test #2:

1 +
2 +
3 +
4 . 1
5 . 2
6 . 3
7 . 4
8 . 5
9 . 6
603 . 1
604 . 2
605 . 3
1203 . 1
1204 . 2
1205 . 3
1206 +
1207 +
1208 +
1209 . 2
1806 +
1806 +
1808 +


Could you please tell me how did you make 1351? I get WA at #4, same as you did... Thanks
About problem 1351
Posted by hey, dude! 25 Mar 2005 00:04
First my solution gives WA on such test :
5 1 0 0 1
1
-1 -1
My prog said that bibr kill gnusmus...

Then I understood that my solution was wrong and wrote a new one. Now I check :
1) if we go from first vector (right frontier of fire) to vector of gnusmus and to left frontier in counterclockwise order.
2) if we go from second vector (left frontier of fire) to vector of gnusmus and to right frontier in clockwise order.

If this two things are true then gnusmus is in the sector of fire => writeln('YES')

That is all :-). See my code in 1351 forum.

P. S. Thanks a lot for the test to 1037. Now I have AC.
Thank you very much!
This test #2 helped me to get AC.

I've made a stupid mistake in program logic...
I would have spent a lot of time looking for it without this test (-:
This is the correct answer for test 2 ? (I can't find any mistake in my code)
Posted by Alexandru Popa 14 Jun 2005 23:23
1
2
3
+
+
+
-
-
-
+
+
+
-
-
-
1
2
3
+
1
4
3

Edited by author 14.06.2005 23:24
What's the correct answer for this test?
Posted by Paul - Dan Baltescu 21 Jul 2006 19:00
Re: What's the correct answer for this test?
Posted by Paul - Dan Baltescu 21 Jul 2006 20:46
Never mind. Yes, the answer is correct :)

Edited by author 24.07.2006 18:48

Edited by author 24.07.2006 18:48