codeIQ クロッシング問題．自分の回答は５秒前後かかる...

answer.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

#define MAX 400000

static void showarray(int *array, int length)
{
    int i;
    printf("[");
    for (i = 0; i < length; i++)
        printf("%d, ", array[i]);
    printf("]\n");
}

static void insert_array(int *array, int length, int pos, int target)
{
    memmove(array + (pos + 1), array + pos, sizeof(int) * (length  - pos));
    *(array + pos) = target;

}
static int search_insert_idx(int *array, int length, int target)
{
    int pibot;
    int pibot_next;
    if (!length) {

        return 0;

    } else {
        pibot = length / 2;
        pibot_next = pibot + 1;
        if (array[pibot] < target) {
            return pibot_next + search_insert_idx(array + pibot_next,length - pibot_next, target);
        } else {
            return search_insert_idx(array,pibot, target);
        }
    }
}

int main(int argc, char const* argv[])
{
    FILE *f;
    char line[BUFSIZ];
    int num;
    int idx;
    int array[MAX];
    int long pos;
    long long sum;

    if (argc != 2) {
        fprintf(stderr, "usage:program filename\n");
        exit(EXIT_FAILURE);
    }

    if ((f = fopen(argv[1], "r")) == NULL) {
        strerror(errno);
        exit(EXIT_FAILURE);
    }

    idx = sum = 0;
    while ((fgets(line, sizeof(line), f)) != NULL) {
        num = atoi(line);
        pos = search_insert_idx(array,idx,num);
        insert_array(array, idx, pos, num);
        sum += (idx - pos);
        idx++;
    }
    fclose(f);
    if (ferror(f)) {
        strerror(errno);
        exit(EXIT_FAILURE);
    }

    printf("%llu\n", sum);

    exit(EXIT_SUCCESS);
}

binary_index_tree.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

#define MAX 400000

static void update(int *array, int size, int idx, int val)
{
    while (idx <= size) {
        array[idx] += val;
        idx += (idx & -idx);
    }
}
static int read(int *array, int size, int idx)
{
    int sum = 0;
    while (idx > 0) {
        sum += array[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

int main(int argc, char const* argv[])
{
    FILE *f;
    char line[BUFSIZ];
    int idx;
    int datalen;
    int endpoints[MAX];
    int bindex[MAX];
    int endpoint;
    long long sum;

    if (argc != 2) {
        fprintf(stderr, "usage:program filename\n");
        exit(EXIT_FAILURE);
    }

    if ((f = fopen(argv[1], "r")) == NULL) {
        strerror(errno);
        exit(EXIT_FAILURE);
    }

    idx = 1;
    while ((fgets(line, sizeof(line), f)) != NULL) {
        endpoints[idx] = atoi(line);
        idx++;
    }
    fclose(f);
    if (ferror(f)) {
        strerror(errno);
        exit(EXIT_FAILURE);
    }

    memset(bindex, 0, sizeof(bindex));
    datalen = --idx;
    sum = 0;
    while (idx > 0) {
        endpoint = endpoints[idx];
        sum += read(bindex, datalen, endpoint);
        update(bindex, datalen, endpoint, 1);
        --idx;
    }

    printf("%llu\n", sum);

    exit(EXIT_SUCCESS);
}

merge_sort.c

#include <alloca.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX 400000

static long long sum = 0;

static void merge_sort(int array[], int length)
{
    int pivot;
    int *tmp;
    int aidx;
    int tidx;
    int right, left;

    tmp = alloca(sizeof(int) * length);

    if (length == 1)
       return;

    pivot = length / 2;
    merge_sort(array,pivot);
    merge_sort(array + pivot, length - pivot);
    /*
     *  ここまでの結果
     *                                 元の配列
     * +------------------+--------------------+
     * |小              大|小                大|
     * +------------------+--------------------+
     */

    tidx = 0;
    /* 前半を順に作業配列へ */
    for (aidx = 0; aidx < pivot; aidx++)
        tmp[tidx++] = array[aidx];

    /* 後半を逆順に作業配列へ */
    for (aidx = length -1; aidx >= pivot; aidx--)
        tmp[tidx++] = array[aidx];
    /*
     *  ここまでの結果
     *                                 作業配列
     * +------------------+--------------------+
     * |小              大|大                小|
     * +------------------+--------------------+
     */

    /*
     * 作業配列の両側から元の配列へ上書きする
     * 中心の境界が番兵となり, 突き抜けることはない
     */
    left = 0; right = length -1;
    for (aidx = 0; aidx < length; aidx++) {
        if (tmp[left] <= tmp[right])
            array[aidx] = tmp[left++];
        else {
            array[aidx] = tmp[right--];
            sum += pivot - left; /*逆転数*/
        }
    }
}

int main(int argc, char const* argv[])
{
    FILE *f;
    char line[BUFSIZ];
    int idx;
    int array[MAX];
    clock_t start, end;

    start = clock();;
    if (argc != 2) {
        fprintf(stderr, "usage:program filename\n");
        exit(EXIT_FAILURE);
    }

    if ((f = fopen(argv[1], "r")) == NULL) {
        strerror(errno);
        exit(EXIT_FAILURE);
    }

    idx = 0;
    while ((fgets(line, sizeof(line), f)) != NULL) {
        array[idx] = atoi(line);
        idx++;
    }

    fclose(f);
    if (ferror(f)) {
        strerror(errno);
        exit(EXIT_FAILURE);
    }

    merge_sort(array,idx);
    end = clock();

    printf("sum = %lld, time = %.2fsec\n", sum, (end - start)/(double)CLOCKS_PER_SEC);

    exit(EXIT_SUCCESS);
}