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

Tác giả: ladpro98

Ngôn ngữ: Pascal

program NKSGAME;
uses    math;
const   maxn=200005;
        fi='';
type    e=record
                v,p:longint;
        end;
var     a:array[1..maxn] of e;
        n,i,x,pa,pb,res:longint;
        inp:text;

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

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

begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do begin
                read(inp,x);
                a[i].v:=x;
                a[i].p:=1;
        end;
        for i:=n+1 to 2*n do begin
                read(inp,x);
                a[i].v:=-x;
                a[i].p:=2;
        end;
        n:=2*n;res:=high(longint);
        sort(1,n);
        for i:=1 to n do begin
                if (a[i].p=2) then begin
                        if pa>0 then
                        res:=min(res,abs(a[i].v-a[pa].v));
                        pb:=i;
                end;
                if (a[i].p=1) then begin
                        if pb>0 then
                        res:=min(res,abs(a[i].v-a[pb].v));
                        pa:=i;
                end;
        end;
        write(res);
end.

Download