Cod sursa(job #253109)

Utilizator MciprianMMarginean Ninu Ciprian MciprianM Data 5 februarie 2009 14:08:44
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<cstring>
using namespace std;
int a[100000];
int b[100000],l, ant[100000];
ofstream g("scmax.out");
void afis(int poz){
  if(poz!=-1){
    afis(ant[poz]);
    g<<a[poz]<<' ';
  }
}
int main(){
  int i, n, pas, j;
  ifstream f("scmax.in");
  f>>n;
  for(i=0;i<n;i++)
    f>>a[i];
  f.close();
  b[l++]=0;
  memset(ant,-1,sizeof(ant));
  for(i=1;i<n;i++)
  {
    for(pas=1;pas<=l;pas<<=1);
    for(j=l-1;pas;pas>>=1)
      if(j-pas>=0&&a[b[j-pas]]>=a[i])
        j-=pas;
    if(j==l-1&&a[b[j]]<a[i]){
      b[l++]=i;
      ant[i]=b[l-2];
    }
    else{
      b[j]=i;
      if(j!=0)
        ant[i]=b[j-1];
      else ant[i]=-1;
    }
  }
  g<<l<<'\n';
  afis(b[l-1]);
  g<<'\n';
  g.close();
  return 0;
}