Cod sursa(job #481883)

Utilizator 05_YohnE1 La5c01 05_Yohn Data 1 septembrie 2010 21:53:05
Problema Statistici de ordine Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.54 kb
{$s-}
var a:array[1..3000000]of longint;
buf:array[1..1 shl 17]of char;
n,k,i,p,m:longint;
s:string[255];

function parse:longint;
var aux:longint;
begin
aux:=0;
while (s[p]>='0') and (s[p]<='9') and (p<=m) do begin
       aux:=aux*10+ord(s[p])-48;
       if p=m then begin
          read(s);
          p:=0;
          m:=length(s);
       end;
       inc(p);
end;

while ((s[p]<'0') or (s[p]>'9'))and(s<>'') do begin
      inc(p);
      if p>m then begin
         read(s);
         p:=1;
         m:=length(s);
      end;
end;
parse:=aux;
end;


function partition(p,q:longint):longint;
var x,i,j,aux:longint;
begin
randomize;
x:=random(q-p+1)+p;
aux:=a[p]; a[p]:=a[x]; a[x]:=aux;
x:=a[p];
i:=p;
for j:=p+1 to q do
    if a[j]<=x then begin
       inc(i);
       aux:=a[i]; a[i]:=a[j]; a[j]:=aux;
       end;
aux:=a[p]; a[p]:=a[i]; a[i]:=aux;
partition:=i;
end;

function RandSel(p,q,i:longint):longint;
var r,k:longint;
begin
if p=q then RandSel:=a[p]
       else begin
            r:=partition(p,q);
            k:=r-p+1;
            if k=i then RandSel:=a[r]
                   else begin
                        if i<k then RandSel:=RandSel(p,r-1,i)
                               else RandSel:=RandSel(r+1,q,i-k);
                        end;
            end;
end;


begin
assign(input,'sdo.in');
reset(input);
SETTEXTBUF(input,buf);
assign(output,'sdo.out');
rewrite(output);
readln(n,k);
read(s);
m:=length(s);
p:=1;
for i:=1 to n do a[i]:=parse;

write(RandSel(1,n,k));
close(output);
end.