Pagini recente » Cod sursa (job #1577142) | Cod sursa (job #2586529) | Cod sursa (job #288433) | Cod sursa (job #195972) | Cod sursa (job #1127741)
#include <cstdio>
#include <algorithm>
using namespace std;
int v[100100], q[100100], p[100100], poz, lg, s[100100], n, nr,MAX;
void citire()
{
int i;
scanf("%d", &n);
for(i=1;i<=n;++i)
scanf("%d", &v[i]);
}
int insert(int k, int lo, int hi)
{
int mid=(lo+hi)/2;
if(lo==hi)
{
if(hi>lg)
q[++lg+1]=MAX;
q[lo]=k;
return lo;
}
else
if(k<q[mid]) return insert(k, lo, mid);
else
if(k>q[mid])
return insert(k, mid+1, hi);
}
void construire_S()
{
int i=lg;
int poz=n;
while(i)
{
while(poz)
{
if(p[poz]==i)
{
s[++nr]=v[poz];
break;
}
poz--;
}
i--;
}
}
void afisare()
{
int i;
printf("%d\n", lg);
for(i=nr;i>=1;--i)
printf("%d ", s[i]);
}
void construire_QP()
{
int i;
for(i=1;i<=n;++i)
{
if(!binary_search(q+1, q+lg+1, v[i]))
p[i]=insert(v[i], 1, lg+1);
}
}
void rezolva_problema()
{
citire();
construire_QP();
construire_S();
afisare();
}
int main()
{
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
MAX=300;
rezolva_problema();
return 0;
}