Cod sursa(job #824116)

Utilizator dragogoshikDragos Badea dragogoshik Data 25 noiembrie 2012 21:05:26
Problema Subsir crescator maximal Scor 0
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 || mid == 0)
                return mid;

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

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

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