Cod sursa(job #824034)

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

#define INT_INF 10000

//functia de cautare cel mai mare subsir crescator

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

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;
}

int main(int argc,char **argv) {
        int i, tmp, lungime = -1;
        int *vec,n;
        int A[4000],
            LIS[4000],
            a[4000] = {0};
        //deschidem fisierul de citit

        //citim primul rand din el
        freopen("scmax.in","r",stdin);

	freopen("scmax.out","w",stdout);
        scanf("%d",&n);

        //citim celelate n linii
        for(i=0;i<n;i++) {

       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);
      
	printf("%d\n",lungime);
        for (i = 0; i < lungime+1; ++i) {
                printf("%d ",vec[i]);


        }


        return 0;
}