Pagini recente » Borderou de evaluare (job #1829462) | Borderou de evaluare (job #2201797) | Cod sursa (job #881604) | Borderou de evaluare (job #842092) | Cod sursa (job #1371905)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
long long a[100001],poz[100001],st[100001],n,i,nr,Max,j,k,x,aux,c[100001];
ifstream f("scmax.in");
ofstream g("scmax.out");
int cautare_binara(int a)
{
int s=1;
int d=nr;
sort(st+1,st+nr+1);
bool OK=true;
while (s<=d && OK==true)
{
if (st[(s+d)/2]==(a+1)) OK=false;
else
{
if (st[(s+d)/2]>(a+1)) s++;
else d--;
}
}
if (OK==true) return (s+d)/2;
else return s;
}
int main()
{
f>>n;
for (i=1; i<=n; i++) f>>a[i];
poz[1]=1;
st[1]=a[1];
nr=1;
for (i=2; i<=n; i++)
{
if (a[i]>st[nr])
{
st[++nr]=a[i];
poz[i]=nr;
}
else
{
if (a[i]!=st[nr])
{
x=cautare_binara(a[i]);
st[x]=a[i];
poz[i]=x;
}
else poz[i]=poz[i-1];
}
}
Max=0;
for (i=1; i<=n; i++)
{
if (poz[i]>Max) Max=poz[i];
}
g<<Max<<'\n';
nr=0;
for (i=1; i<=n; i++)
{
aux=i;;
if (poz[i]==Max)
{
for (k=1; k<=Max; k++)
{
c[++nr]=a[aux];
for (j=aux; j>=1; j--) if (a[j]<a[aux] && poz[j]==(poz[aux]-1))
{
break;
}
aux=j;
}
}
}
for (i=nr; i>=1; i--) g<<c[i]<<' ';
return 0;
}