Cod sursa(job #480145)

Utilizator 05_YohnE1 La5c01 05_Yohn Data 26 august 2010 15:41:58
Problema Statistici de ordine Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.08 kb
var a:array[1..3000000]of longint;
i,n,k:longint;

function partitie(s,d:longint):longint;
var i,j,piv,sol,aux:longint;
begin
i:=s; j:=d;
randomize;
piv:=a[s+random(d-s+1)];
while true do begin
      while a[i]<piv do inc(i);
      while a[j]>piv do dec(j);
      if i<j then begin
                  aux:=a[i];
                  a[i]:=a[j];
                  a[j]:=aux;
                  inc(i); dec(j);
                  end
                  else begin
                       sol:=j;
                       break;
                       end;
end;
partitie:=sol;
end;

function DI(s,d,k:longint):longint;
var x,r:longint;
begin
if s=d then DI:=a[s]
else if s<d then begin
        x:=partitie(s,d);
        r:=x-s+1;
        if r<>k then begin
           if r>k then DI:=DI(s,x-1,k)
                  else DI:=DI(x+1,d,k-r);
           end
           else DI:=a[r];
        end;
end;


begin
assign(input,'sdo.in');
reset(input);
assign(output,'sdo.out');
rewrite(output);
read(n,k);
for i:=1 to n do read(a[i]);
write(DI(1,n,k));
close(output);
end.