Cod sursa(job #401464)

Utilizator nickyyLal Daniel Emanuel nickyy Data 22 februarie 2010 21:15:05
Problema Cautare binara Scor 60
Compilator fpc Status done
Runda Arhiva educationala Marime 1.09 kb
const infile='cautbin.in';
  outfile='cautbin.out';
  maxnm=100000;
var v:array[1..maxnm]of longint;
  n,m,x,r,step,i:longint;
  op:0..2;
  fi,fo:text;

 function eg_mare(lg,x:longint):longint;
 var i:longint;
 begin
  i:=0;
  repeat
    if(i+lg<=n)and(v[i+lg]<=x)then inc(i,lg);
    lg:=lg shr 1;
  until(lg=0)or(v[i]>=x);
  eg_mare:=i;
 end;

 function mic(lg,x:longint):longint;
 var i:longint;
 begin
   i:=n;
   repeat
     if(i-lg>0)then
       if(v[i-lg]>=x)then dec(i,lg);
     lg:=lg shr 1;
   until(lg=0)or(v[i]<x);
   mic:=i;
 end;

begin
 assign(fi,infile); reset(fi);
 assign(fo,outfile); rewrite(fo);
 readln(fi,n); for i:=1 to n do read(fi,v[i]);
 step:=1;
 while(step<n)do step:=step shl 1;
 if(step>n)then step:=step shr 1;
 readln(fi,m);
 while(m>0)do begin
   readln(fi,op,x);
   case op of
     0:begin
         r:=eg_mare(step,x);
         if(v[r]<>x)then writeln(fo,-1)
         else writeln(fo,r);
         end;
     1:writeln(fo,eg_mare(step,x));
     2:writeln(fo,mic(step,x));
     end;
   dec(m);
   end;
 close(fi); close(fo);
end.