FIRS - Hàng cây

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=100000;
var n,re,dem:longint;
    a,b,d:array[1..maxn] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     for i:=1 to n do
     begin
          read(a[i]);
          b[i]:=i;
     end;
     close(input);
end;

procedure sort(l,r:longint);
var i,j,x,y,xx:longint;
begin
     i:=l; j:=r; x:=a[(i+j) div 2]; xx:=b[(i+j) div 2];
     repeat
           while (a[i]<x) or ((a[i]=x) and (b[i]<xx)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (b[j]>xx)) do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=b[i]; b[i]:=b[j]; b[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function check(x:longint):boolean;
begin
     check:=(x>0) and (x<=n);
end;

procedure pr;
var cur,i:longint;
begin
     sort(1,n);
     fillchar(d,sizeof(d),0);
     dem:=0; re:=0; cur:=1;
     repeat
           inc(re);
           while d[b[cur]]=1 do inc(cur);
           d[b[cur]]:=1; inc(dem);
           for i:=0 to 1 do
               if check(b[cur]-1+2*i) and (d[b[cur]-1+2*i]=0) then
               begin
                    inc(dem); d[b[cur]-1+2*i]:=1;
               end;
           inc(cur);
     until dem=n;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download