KMIN - KMIN

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
var
  i,n,m,k,hsize,val,ia,ib:longint;
  a,b,h,ha,hb:array[1..50111] of longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure swapH(a,b:longint);
    begin
      swap(h[a],h[b]);
      swap(ha[a],ha[b]);
      swap(hb[a],hb[b]);
    end;

procedure down(i:longint);
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and (h[j+1]<h[j]) then inc(j);
          if h[j]<h[i] then swapH(i,j);
          i:=j; j:=i shl 1;
        end;
    end;

procedure up(i:longint);
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and (h[i]<h[j]) do
        begin
          swapH(i,j);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u,a,b:longint);
    begin
      inc(hsize);
      h[hsize]:=u;
      ha[hsize]:=a;
      hb[hsize]:=b;
      up(hsize);
    end;

procedure pop(var u,a,b:longint);
    begin
      u:=h[1];
      a:=ha[1];
      b:=hb[1];
      swapH(1,hsize);
      dec(hsize);
      down(1);
    end;

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

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

begin
  read(n,m,k);
  for i:=1 to n do read(a[i]);
  for i:=1 to m do read(b[i]);
  sortA(1,n);
  sortB(1,m);

  for i:=1 to n do push(a[i]+b[1],i,1);

  for i:=1 to k do
    begin
      pop(val,ia,ib);
      writeln(val);
      if ib<m then push(a[ia]+b[ib+1],ia,ib+1);
    end;
end.

Download