Cod sursa(job #750331)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 21 mai 2012 21:27:59
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<cstdio>
using namespace std;
int i, m, n, j, a[100001], p[100001], q[100001];
int cb(int st, int dr, int mi){
    int mij=(st+dr)/2;
    if (st-dr<=1) {m=mi; return 0;}
    if (q[mij]<a[i]) cb(mij, dr, mij); else cb(st, mij, mi);
}
int main(){
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d", &n);
    for (i=1;i<=n;i++) {scanf("%d", &a[i]); p[i]=0; q[i]=0;}
    p[1]=1; q[1]=a[1]; q[0]=1;
    for (i=2;i<=n;i++) {
        m=-1;
        if (q[0]<=20) {
            for (j=1;j<=q[0];j++) if (a[i]<=q[j]) {m=j; break;}
            if (m<0) {p[i]=q[0]+1; q[0]++; q[q[0]]=a[i];}
            if (m>0) q[m]=a[i];
        } else
        {if (q[0])cb(1, q[0], -1); if (m>0) {p[i]=++q[0]; q[0]=a[i];} else q[m]=a[i];}
    }
    printf("%d\n", q[0]); m=1;
    for (i=1;i<=n;i++) {if (p[i]==m) {m++; printf("%d ", a[i]);} if (m>q[0]) break;}
    printf("\n");
    return 0;
}