NKSGAME - VOI08 Trò chơi với dãy số

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
var i,j,n,re:longint;
    a,b:array[1..100000] of longint;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
        i:=l; j:=r; x:=a[(i+j) shr 1];
        repeat
                while a[i]<x do i:=i+1;
                while a[j]>x do j:=j-1;
                if i<=j then
                begin
                        y:=a[i]; a[i]:=a[j]; a[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 bs(x:longint):longint;
var l,r,m,i:longint;
begin
        l:=1; r:=n;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[m]=x then break;
                if a[m]<x then l:=m+1
                else r:=m-1;
        end;
        r:=maxlongint;
        for i:=m-1 to m+1 do
            if (i>0) and (i<=n) then
               r:=min(r,abs(a[i]-x));
        bs:=r;
end;

begin
        read(n);
        for i:=1 to n do read(a[i]);
        for i:=1 to n do read(b[i]);
        sort(1,n);
        re:=abs(a[1]+b[1]);
        for i:=1 to n do
        begin
                j:=bs(-b[i]);
                if j<re then re:=j;
                if re=0 then break;
        end;
        writeln(re);
end.

Download