|
|
back to boardI've got WA on test 2 a lot of times :-( Help me please! 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! 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 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) 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? Re: What's the correct answer for this test? Never mind. Yes, the answer is correct :) Edited by author 24.07.2006 18:48 Edited by author 24.07.2006 18:48 |
|
|