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!

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

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.

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 (-:

1
2
3
+
+
+
-
-
-
+
+
+
-
-
-
1
2
3
+
1
4
3

Edited by author 14.06.2005 23:24

Never mind. Yes, the answer is correct :)

Edited by author 24.07.2006 18:48

Edited by author 24.07.2006 18:48