C11CAVE - Hang động

Tác giả: ladpro98

Ngôn ngữ: Pascal

program c11cave;
uses    math;
const   fi='';
        up=0;down=1;
        maxN=500005;
var     a:array[up..down,0..maxN] of longint;
        f1,f2:array[1..maxN] of longint;
        n,h,res,c:longint;

procedure input;
var     f:text;
        i:longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n,h);
        for i:=1 to n do
        begin
                if odd(i) then readln(f,a[down,i div 2 +1])
                else readln(f,a[up,i div 2]);
        end;
        close(f);
end;

procedure swap(k,i,j:longint);
var     t:longint;
begin
        t:=a[k,i];
        a[k,i]:=a[k,j];
        a[k,j]:=t;
end;

procedure sort(k,l,r:longint);
var     p,i,j:longint;
begin
        if l>=r then exit;
        p:=a[k,random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while a[k,i]<p do inc(i);
                while a[k,j]>p do dec(j);
                if i<=j then
                begin
                        if i<j then swap(k,i,j);
                        inc(i);dec(j);
                end;
        until i>j;
        sort(k,l,j);sort(k,i,r);
end;

procedure process;
var     i,j:longint;
begin
        j:=1;
        for i:=1 to H do
        begin
                while (j<=N div 2) and (a[down,j]<i) do inc(j);
                f1[i]:=n div 2-j+1;
        end;
        j:=1;
        for i:=H downto 1 do
        begin
                while (j<=N div 2) and (a[up,j]<(H-i+1)) do inc(j);
                f2[i]:=n div 2-j+1;
        end;
        res:=maxN;
        for i:=1 to H do res:=min(res,f1[i]+f2[i]);
        for i:=1 to H do if (f1[i]+f2[i]=res) then inc(c);
end;

begin
        input;
        sort(up,1,n div 2);
        sort(down,1,n div 2);
        process;
        write(res,' ',c);
end.

Download