Cod sursa(job #824129)

Utilizator dragogoshikDragos Badea dragogoshik Data 25 noiembrie 2012 21:29:53
Problema Subsir crescator maximal Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.75 kb
#include <stdio.h>
#include <malloc.h>

int binaryInsert(int value, int left, int right, int *vector){
    int mid;

    while(1){
        mid = (left + right) / 2;

        if (vector[mid] == value)
            return mid;

        if (vector[mid] < value){
            if (left == right)
                return mid + 1;

            left = mid + 1;
            continue;
        }

        if (vector[mid] > value){
            if (left == right)
                return mid;

            right = mid;
            continue;
        }
    }

    return left;
}

int main(void){

    int elemCount, *elements, *length, maxLen = 0, *order;
    FILE *in    = fopen("scmax.in", "r");
    FILE *out   = fopen("scmax.out", "w");

    fscanf(in, "%d", &elemCount);
    elements    = (int*) malloc((elemCount + 1) * sizeof(int));
    length      = (int*) malloc((elemCount + 1) * sizeof(int));
    order       = (int*) calloc((elemCount + 1), sizeof(int));

    int i, insert;
    fscanf(in, "%d", &elements[0]);
    order[0]    = elements[0];
    length[0]   = 0;

    int j;
    for (i = 1; i < elemCount; i++){
        fscanf(in, "%d", &elements[i]);
        insert = binaryInsert(elements[i], 0, maxLen, order);

        order[insert]   = elements[i];
        length[i]       = insert;

        if (insert > maxLen)
            maxLen = insert;
    }
    fclose(in);

    i = 0;
    int save = maxLen;
    while (length[i] != maxLen){
        i ++;
    }

    while (i >= 0){
        if (length[i] == maxLen)
            order[maxLen--] = elements[i];

        i --;
    }

    fprintf(out, "%d\n", save + 1);
    for (i = 0; i <= save; i++){
        fprintf(out, "%d ", order[i]);
    }
    fprintf(out, "\n");
    fclose(out);

    free(elements);
    free(length);
    free(order);
    return 0;
}