Cod sursa(job #823976)

Utilizator mihaitensormihai ilie mihaitensor Data 25 noiembrie 2012 19:34:36
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 2.41 kb
#include <stdio.h>
#include <stdlib.h>

#define INT_INF 10000

int cauta(int *lista, int stanga, int dreapta, int cheie) {
        int mijloc;

        for (mijloc= (stanga+dreapta)/2; stanga <= dreapta; mijloc= (stanga+dreapta)/2) {
                if (lista[mijloc] > cheie) {
                        dreapta = mijloc- 1;
                } else if (lista[mijloc] == cheie) {
                        return mijloc;
                } else if (mijloc+1 <= dreapta && lista[mijloc+1] >= cheie) {
                        lista[mijloc+1] = cheie;
                        return mijloc+1;
                } else {
                        stanga = mijloc+ 1;
                }
        }
        if (mijloc== stanga) {
                lista[mijloc] = cheie;
                return mijloc;
        }
        lista[mijloc+1] = cheie;
        return mijloc+1;
}

void swap(int *a, int *b)
{
  int t=*a; *a=*b; *b=t;
}
void sorteaza(int arr[], int beg, int end)
{
  if (end > beg + 1)
  {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    swap(&arr[--l], &arr[beg]);
    sorteaza(arr, beg, l);
    sorteaza(arr, r, end);
  }
}

int main(int argc,char **argv) {
        char string[1000];
        FILE *fin,*fout;
        int i, tmp, lungime = -1;
        int *vec,n=40;
        int A[40000],
            LIS[40],
            a[7] = {0};
        //deschidem fisierul de citit

        //citim primul rand din el
        freopen(argv[1],"r",stdin);

        scanf("%d",&n);

        //citim celelate n linii
        for(i=0;i<n;i++) {
            getchar();
       scanf("%d",&A[i]);

        }

        LIS[0] = A[0];
        for (i = 1; i < n; ++i) {
                LIS[i] = INT_INF;
        }

        for (i = 1; i < n; ++i) {
                a[i] = cauta(LIS, 0, i, A[i]);
                if (lungime < a[i]) {
                        lungime = a[i];
                }
        }

        vec = (int*) malloc((lungime+1) * sizeof(int));
        for (i = n-1, tmp = lungime; i >= 0; --i) {
                if (a[i] == tmp) {
                        vec[tmp] = i;
                        --tmp;
                }
        }

        for(i=0;i<lungime+1;i++)
            vec[i]++;


        sorteaza(vec,1,lungime);
        freopen(argv[2],"w",stdout);
        for (i = 0; i < lungime+1; ++i) {
                printf("%d ",vec[i]);


        }


        return 0;
}