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 1251. Cemetery Manager

I got WA on test 6, Can anybody give me some tests?Here is my program.
Posted by Mill 20 May 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.