RIDDLE - Bí hiểm

Tác giả: ladpro98

Ngôn ngữ: Pascal

program riddle;
uses    math;
const   maxn=trunc(1e5)+5;
        fi='';
var     a,org:array[1..maxn] of longint;
        l,r,i,tt,t,n,m,res,k:longint;
        inp:text;

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

function ok(p:longint):boolean;
var     t,i:longint;
begin
        for i:=1 to p do a[i]:=org[i];
        sort(1,p);t:=0;
        for i:=1 to p do begin
                if a[i]<=t+1 then inc(t,a[i])
                else break;
                if t>=k then exit(true);
        end;
        if t<k then exit(false);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,t);
        for tt:=1 to t do begin
                readln(inp,n,k);
                for i:=1 to n do read(inp,org[i]);
                l:=1;r:=n;res:=-1;
                while l<=r do begin
                        m:=(l+r) shr 1;
                        if ok(m) then begin
                                res:=m;
                                r:=m-1;
                        end
                        else    l:=m+1;
                end;
                writeln(res);
        end;
end.

Download