Pagini recente » Cod sursa (job #803985) | Cod sursa (job #2772674) | Cod sursa (job #1555818) | Cod sursa (job #2669804) | Cod sursa (job #2574447)
#include <bits/stdc++.h>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int const lim = 100001;
int n,v[lim],d[lim],t,mx;
struct ob
{
int poz,vl;
}c[lim];
vector < int > q;
bool comp(ob x, ob y)
{
return x.vl<y.vl;
}
int caut(int val , int st , int dr)
{
int mij=(st+dr)/2;
if(c[mij].vl<val && c[mij+1].vl>=val)
return c[mij].poz;
if(c[mij].vl<val && mij==t)
return c[mij].poz;
if(c[mij].vl<val && c[mij+1].vl<val)
return caut(val,mij+1,dr);
if(c[mij].vl>=val && mij>1)
return caut(val,st,mij);
return -1;
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
{
in>>v[i];
}
d[1]=1;
t++;
c[t].vl=v[1];
c[t].poz=1;
for(int i=2;i<=n;i++)
{
sort(c+1,c+1+t,comp);
int x=caut(v[i],1,t);
if(x==-1)
d[i]=1;
else
d[i]=d[x]+1;
t++;
c[t].vl=v[i];
c[t].poz=i;
if(d[i]>mx) mx=d[i];
}
out<<mx<<'\n';
for(int i=n;i>=1;i--)
if(d[i]==mx)
{
q.push_back(v[i]);
mx--;
}
for(int i=q.size()-1;i>=0;i--)
out<<q[i]<<" ";
}