Cod sursa(job #181276)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 18 aprilie 2008 09:59:22
Problema Subsir crescator maximal Scor 20
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 kb
var a,b,c,m:array[1..100000] of longint;
    f,g:text;
    nr,i,max,poz,n,x:longint;

function caut(x:longint):longint;
 var rasp,st,dr,mij:longint;
 begin
  st:=1; dr:=nr+1; rasp:=0;
  while st<=dr do begin
   mij:=(st+dr) shr 1;
   if (b[mij]<x) and ((mij=1) or (b[mij-1]>=x)) then begin
    rasp:=mij;
    break;
   end
   else
    if (b[mij]>x) then
     st:=mij+1
    else
     dr:=mij-1;
  end;
  if rasp=nr+1 then
   inc(nr);
  caut:=rasp;
 end;

begin
 assign(f,'scmax.in'); reset(f);
 assign(g,'scmax.out'); rewrite(g);
 read(f,n);
 nr:=0;
 for i:=1 to n do
  read(f,a[i]);
 for i:=1 to n do begin
  x:=caut(a[i]);
  inc(m[x]);
  c[i]:=m[x];
  b[x]:=a[i];
 end;
 poz:=0; max:=0;
 for i:=1 to n do
  if c[i]>max then begin
   poz:=i;
   max:=c[i];
  end;
 writeln(g,max);
 nr:=1;
 b[nr]:=a[poz];
 for i:=n downto 1 do
  if (a[i]<a[poz]) and (c[i]+1=c[poz]) then begin
   inc(nr);
   b[nr]:=a[i];
   poz:=i;
  end;
 for i:=nr downto 1 do
  write(g,b[i],' ');
 writeln(g);
 close(f); close(g);
end.