Cod sursa(job #824070)

Utilizator dragogoshikDragos Badea dragogoshik Data 25 noiembrie 2012 20:39:14
Problema Subsir crescator maximal Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdio.h>
#include <malloc.h>

int binaryInsert(int value, int left, int right, int *vector){
    int mid = (left + right) / 2;

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

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

        return binaryInsert(value, mid + 1, right, vector);
    }

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

        return binaryInsert(value, left, mid - 1, vector);
    }

    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]   = 1;

    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 + 1;

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

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

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

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

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