ACM UVA (10026)

/*
 *******************************************************************************
 *
 * Filename: 10026.c
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

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

struct order {
    int days;
    int cents;
    int pos;
};

struct order order_array[1000];

int compare_order(const void *order1, const void *order2)
{
    int value;
    struct order *order_1 = (struct order *)order1;
    struct order *order_2 = (struct order *)order2;

    value = order_1->days * order_2->cents - order_1->cents * order_2->days;
    if (value < 0) {
        return -1;
    } else if (value == 0) {
        return 0;
    } else {
        return 1;
    }
}

struct order order_aux[1000];
merge(struct order array[], int l, int m, int r)
{
    int i, j, k;

    for (i = l; i <= r; i++) {
        order_aux[i] = array[i];
    }
    for (i = l, j = m+1, k = l; k <= r; k++) {
        if (i > m) {
            array[k] = order_aux[j++];
            continue;
        }
        if (j > r) {
            array[k] = order_aux[i++];
            continue;
        }
        if (0 >= compare_order(&order_aux[i], &order_aux[j])) {
            array[k] = order_aux[i++];
        } else {
            array[k] = order_aux[j++];
        }
    }
}

void mergesort(struct order array[], int l, int r)
{
    int m;
    int i;
    
    if (r <= l) {
        return;
    }

    m = l + (r-l+1)/2 -1;
    mergesort(array, l, m);
    mergesort(array, m+1, r);
    merge(array, l, m, r);
}

int main(int argc, char **argv)
{
    int shoemaker_num = 0;
    int order_num;
    int i, j;
    int tmp;

    scanf("%d\n", &shoemaker_num);
    for (i = 0; i < shoemaker_num; i++) {
        scanf("%d", &order_num);
        
        for (j = 0; j < order_num; j++) {
            scanf("%d %d", &(order_array[j].days), &(order_array[j].cents));
            order_array[j].pos = j+1;
        }
        mergesort(order_array, 0, order_num-1);
        for (tmp = 0; tmp < order_num; tmp++) {
            printf("%d", order_array[tmp].pos);
            if (tmp != order_num-1) {
                printf(" ");
            }
        }
        if (i != shoemaker_num -1) {
            printf("\n\n");
        }
    }
}