Listing: CULMI.PAS



program Crescatoare; 
 var V,Max,Next:array[0..10000]    of Word; 
 N,NSubs:Integer; 
 
 procedure ReadData; 
 var i:Integer; 
 
begin  
 Assign(Input,'cresc.in'); Reset(Input);    
 ReadLn(N); 
 for i:=1 to N do    Read(V[i]); 
 Close(Input) 
 end; 
 
 function BinSearch(W:Word;Lo,Hi:Integer):    
 Integer; 
 { Cauta in vectorul Max, care este    } 
 { sortat descrescator, si returneaza    } 
 { indicele celui mai mare element    mai mic } 
 { decat W. Daca toate elementele sunt    } 
 { mai mari ca W, atunci returneaza    NSubs+1 } 
 var Mid:Integer; 
 begin 
 while Lo<Hi do 
 begin 
 Mid:=(Lo+Hi) div 2; 
 if W>V[Max[Mid]] then    Hi:=Mid 
 else Lo:=Mid+1 
 end; 
 if (Lo>Hi) or (W<=V[Max[Hi]])    
 then BinSearch:=Hi+1 
 else BinSearch:=Hi 
 end; 
 procedure BuildVectors; 
 { Construieste vectorul    Next cu } 
 { inlantuirea subsirurilor    cautate } 
 var NewPlace,i:Integer; 
 begin 
 NSubs:=0; 
 Max[0]:=50001; 
 for i:=1 to N do    
 begin 
 NewPlace:=BinSearch(V[i], 1, NSubs);    
 if NewPlace>NSubs 
 then Inc(NSubs) 
 else Next[Max[NewPlace]]:=i;    
 Max[NewPlace]:=i; 
 Next[i]:=0 
 end 
 end; 
 
 procedure WriteSolution; 
 { Extrage subsirurile,    folosind } 
 { informatia din vectorul    Next. } 
 { Vectorul Max serveste    aici numai ca } 
 { vector caracteristic    al elementelor } 
 { deja tiparite } 
 var Marker,Ind,i:Integer; 
 begin 
 for i:=1 to N do    Max[i]:=0; 
 Assign(Output,'cresc.out'); 
 Rewrite(Output); 
 WriteLn(NSubs); 
 Marker:=0; 
 for i:=1 to NSubs do    
 begin 
 
repeat  
Inc(Marker) 
 until Max[Marker]=0; 
 Ind:=Marker; 
 repeat 
 Max[Ind]:=1; 
 Write(Ind,' '); 
 Ind:=Next[Ind] 
 until Ind=0; 
 Writeln 
 end; 
 Close(Output) 
 end; 
 
 Begin 
 ReadData; 
 BuildVectors; 
 WriteSolution 
 End.