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.