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

Обсуждение задачи 1251. Менеджер кладбища

I got WA on test 6, Can anybody give me some tests?Here is my program.
Послано Mill 20 май 2004 08:12
const inp='';
      out='';
      daysize1=1001;
      daysize2=101;
      maxn=151;
      c:array[1..8,1..2] of longint=((-1,0),(1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1));

type datatype=array[0..maxn*maxn] of longint;

var client,size,ans,n,m:longint;
    treeperson,persontree,f,heavityperson,personheavity,h:datatype;

procedure add(p,data:longint);

begin
  while p<=size do begin
    inc(f[p],data);
    p:=p or (p-1)+1;
  end;
end;

function calc(p:longint):longint;

var tmp:longint;

begin
  tmp:=0;
  while p>0 do begin
    inc(tmp,f[p]);
    p:=p and (p-1);
  end;
  calc:=tmp;
end;

procedure heavity(p,nn:longint);

var tmph,tmpp,j:longint;

begin
  tmph:=h[p];tmpp:=heavityperson[p];
  j:=p shl 1;
  while j<=nn do begin
    if (j<nn)and(h[j+1]<h[j]) then inc(j);
    if h[j]<tmph then begin
      h[p]:=h[j];
      heavityperson[p]:=heavityperson[j];
      personheavity[heavityperson[p]]:=p;
      p:=j;j:=p shl 1;
    end
    else j:=nn+1;
  end;
  h[p]:=tmph;heavityperson[p]:=tmpp;
  personheavity[heavityperson[p]]:=p;
end;

procedure updata(p:longint);

var tmpp,tmph,j:longint;

begin
  j:=p shr 1;tmph:=h[p];tmpp:=heavityperson[p];
  while j>0 do
    if h[j]>tmph then begin
      h[p]:=h[j];heavityperson[p]:=heavityperson[j];
      personheavity[heavityperson[p]]:=p;
      p:=j;j:=p shr 1;
    end
    else break;
  h[p]:=tmph;heavityperson[p]:=tmpp;
  personheavity[heavityperson[p]]:=p;
end;

procedure main;

var nowx,z,nowy,xcurrent,ycurrent,now,w,current,l,r,day,d,i:longint;
    x:char;

begin
  assign(input,inp);reset(input);
  readln(n,m);size:=n*m;
  w:=0;
  repeat
    read(day);
    while (w>0)and(h[1]<=day) do begin
      now:=heavityperson[1];
      h[1]:=h[w];
      heavityperson[1]:=heavityperson[w];
      personheavity[heavityperson[1]]:=1;
      dec(w);
      if w>0 then heavity(1,w);
      add(persontree[now],-1);
      persontree[now]:=0;
    end;
    read(x);
    while (x<>'d')and(x<>'v') do read(x);
    if (x='d') then begin
      inc(client);l:=1;r:=size;
      if w<size then begin
        while l<r do begin
          d:=(l+r) shr 1;
          if calc(d)<d then r:=d else l:=d+1;
        end;
        add(r,1);
        treeperson[r]:=client;
        inc(w);
        heavityperson[w]:=client;
        h[w]:=day+daysize1;
        personheavity[client]:=w;
        persontree[client]:=r;
        updata(w);
      end
      else inc(ans);
    end
    else if x='v' then begin
      read(current);
      if persontree[current]>0 then begin
        h[personheavity[current]]:=day+daysize1;
        heavity(personheavity[current],w);
        xcurrent:=(persontree[current]-1) div m+1;
        ycurrent:=persontree[current]+m-xcurrent*m;
        for i:=1 to 8 do begin
          nowx:=xcurrent+c[i,1];
          nowy:=ycurrent+c[i,2];
          if (nowx>=1)and(nowx<=n)and(nowy>=1)and(nowy<=m) then
            z:=(nowx-1)*m+nowy
          else z:=0;
          if treeperson[z]>0 then
            if h[personheavity[treeperson[z]]]<day+daysize2 then begin
              h[personheavity[treeperson[z]]]:=day+daysize2;
              heavity(personheavity[treeperson[z]],w);
            end;
        end;
      end;
    end;
  until seekeof(input);
  assign(output,out);rewrite(output);
  writeln(ans);
  close(output);
end;

Begin
  Main;
End.