Cod sursa(job #752541)

Utilizator alexa_mihaltanMihaltan Alexandra alexa_mihaltan Data 28 mai 2012 20:34:05
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#define MAX 100001
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[MAX],b[MAX],c[MAX],na,nb;
int poz;
void readfromfile(int val)
{
int st=1,end=nb,mij;poz=-1;
while(st<=end)
{
mij=(st+end)/2;
if(b[mij]>=val)
{
poz=mij;
end=mij-1;
}
else st=mij+1;
}
}
int main()
{
int i,j;
fin>>na;
for(i=1;i<=na;i++)
{
fin>>a[i];
readfromfile(a[i]);
if(poz==-1)
b[c[i]=++nb]=a[i];
else
b[c[i]=poz]=a[i];
}
fout<<nb<<'\n';
for(i=na,j=nb;j>0;j--)
{
while(c[i]!=j) i--;
b[j]=a[i];
}
for(i=1;i<=nb;i++)
fout<<b[i]<<' ';
fout<<"\n";
return 0;
}