ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1037. Управление памятью

I've got WA on test 2 a lot of times :-( Help me please!
Послано hey, dude! 24 мар 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!
Послано Cybernetics Team 24 мар 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
Послано hey, dude! 25 мар 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)
Послано Alexandru Popa 14 июн 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?
Послано Paul - Dan Baltescu 21 июл 2006 19:00
Re: What's the correct answer for this test?
Послано Paul - Dan Baltescu 21 июл 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