Cod sursa(job #182950)

Utilizator zbarniZajzon Barna zbarni Data 21 aprilie 2008 15:41:24
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream.h>
#define g 100002
using namespace std;

int a[g],b[g],c[g],d[g],n,s;
int poz,ok;
ifstream be ("scmax.in");
ofstream ki ("scmax.out");

void binsearch (int value)
 {
  int left=1,middle,end=s; poz=-1;
  while (left<=end)
   {
    middle=(left+end)/2;
    if (b[middle]>=value)
      {
       poz=middle;
       end=middle-1;
      }
    else
      left=middle+1;
   }
 }

int main()
 {
  int i;
  be>>n;
  for (i=1;i<=n;i++)
    {
     be>>a[i];
     binsearch (a[i]);
     if (poz==-1)
       {
	b[++s]=a[i];
	c[i]=s;
       }
     else
       {
	b[poz]=a[i];
	c[i]=poz;
       }
    }
  be.close();
  ok=s;
  ki<<s<<'\n';
  while (ok)
   {
    while (ok!=c[i])
      i--;
    d[ok]=a[i];
    ok--;
   }
  for (i=1;i<=s;i++)
     {
      ki<<d[i];
      if (i<s)
	ki<<" ";
     }
  ki<<'\n';
  ki.close();
  return 0;
 }