KMIN - KMIN

Tác giả: flashmt

Ngôn ngữ: Pascal

const maxn=50020;
type ar=array[1..maxn] of longint;
var n,m,k,nh:longint;
    h,p,a,b,c,d:ar;

procedure sort(var a:ar;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(a,i,r);
     if l<j then sort(a,l,j);
end;

procedure rf;
var i:longint;
begin
     read(m,n,k);
     for i:=1 to m do read(a[i]);
     for i:=1 to n do read(b[i]);
     sort(a,1,m);
     sort(b,1,n);
end;

procedure update(i:longint);
var cha,con:longint;
begin
     con:=p[i];
     if con=0 then
     begin
          inc(nh); con:=nh;
          cha:=con shr 1;
          while (cha>0) and (d[h[cha]]>d[i]) do
          begin
               h[con]:=h[cha];
               p[h[con]]:=con;
               con:=cha;
               cha:=con shr 1;
          end;
          h[con]:=i; p[i]:=con;
     end
     else
     begin
          cha:=con; con:=cha shl 1;
          while con<=nh do
          begin
               if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con);
               if d[h[con]]>=d[i] then break;
               h[cha]:=h[con];
               p[h[cha]]:=cha;
               cha:=con;
               con:=cha shl 1;
          end;
          h[cha]:=i; p[i]:=cha;
     end;
end;

function pop:longint;
var cha,con,x:longint;
begin
     pop:=h[1];
     x:=h[nh]; dec(nh);
     cha:=1; con:=2;
     while con<=nh do
     begin
          if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con);
          if d[x]<=d[h[con]] then break;
          h[cha]:=h[con];
          p[h[cha]]:=cha;
          cha:=con; con:=cha shl 1;
     end;
     h[cha]:=x; p[x]:=cha;
end;

procedure pr;
var i,x:longint;
begin
     for i:=1 to m do
     begin
          c[i]:=1;
          d[i]:=a[i]+b[1];
          update(i);
     end;
     for i:=1 to k do
     begin
          x:=pop;
          writeln(d[x]);
          p[x]:=0;
          if c[x]<n then
          begin
               inc(c[x]);
               d[x]:=a[x]+b[c[x]];
               update(x);
          end;
     end;
end;

begin
     rf;
     pr;
end.

Download