ac1201.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1201;
const
  maxprogs=10001;
var
  heap:array[0..maxprogs]of record fin:longint;pchain:word;end;
  chain:array[0..maxprogs]of record left,right:longint;pheap,pre,next:word;end;
  wait:array[1..maxprogs]of record mem,time:longint;end;
  h,n,a,b,c,f,r,now,p:longint;
function where(mem:longint):word;
  begin
    where:=0;
    while (chain[where].next>0) and
          (chain[chain[where].next].left-chain[where].right<mem) do
      where:=chain[where].next;
  end;
procedure ins(where,fintime,mem:longint);
  var
    p,q:word;
  begin
    inc(n);
    with chain[n] do begin
      left:=chain[where].right;right:=left+mem;
      pre:=where;next:=chain[where].next;
    end;
    chain[where].next:=n;chain[chain[n].next].pre:=n;
    inc(h);p:=h;q:=p shr 1;
    while (p>1) and (fintime<heap[q].fin) do begin
      heap[p]:=heap[q];
      chain[heap[p].pchain].pheap:=p;
      p:=q;q:=p shr 1;
    end;
    with heap[p] do begin fin:=fintime;pchain:=n;end;
    chain[n].pheap:=p;
  end;
function pop:longint;
  var
    p,l,r:word;
  begin
    pop:=heap[1].fin;
    p:=heap[1].pchain;chain[chain[p].pre].next:=chain[p].next;chain[chain[p].next].pre:=chain[p].pre;
    p:=1;l:=2;r:=3;
    repeat
      if (r<h) and (heap[h].fin>heap[r].fin) and (heap[r].fin<heap[l].fin) then begin
        heap[p]:=heap[r];
        chain[heap[p].pchain].pheap:=p;
        p:=r;
      end
      else if (l<h) and (heap[h].fin>heap[l].fin) then begin
        heap[p]:=heap[l];
        chain[heap[p].pchain].pheap:=p;
        p:=l;
      end
      else
        break;
      l:=p*2;r:=l+1;
    until false;
    heap[p]:=heap[h];chain[heap[p].pchain].pheap:=p;
    dec(h);
  end;
begin
  repeat
    h:=1;
    with heap[1] do begin fin:=maxlongint;pchain:=1;end;
    n:=1;
    with chain[0] do begin right:=0;next:=1;end;
    with chain[1] do begin read(left);pheap:=1;pre:=0;next:=0;end;
    f:=1;r:=0;
    repeat
      read(a,b,c);
      if b=0 then a:=maxlongint-1;
      while heap[1].fin<=a do begin
        repeat now:=pop;until heap[1].fin>now;
        while f<=r do begin
          p:=where(wait[f].mem);
          if chain[p].next=0 then break;
          ins(p,now+wait[f].time,wait[f].mem);
          inc(f);
        end;
      end;
      if b=0 then break;
      p:=where(b);
      if chain[p].next>0 then
        ins(p,a+c,b)
      else begin
        inc(r);wait[r].mem:=b;wait[r].time:=c;
      end;
    until false;
    writeln(now);writeln(r);
  until seekeof;
end.