#include "common.h"
#include <stdio.h>

typedef struct {
    int id, arrival_time, duration, start_time, waiting_time;
} CUSTOMER;

int compare_arrival_time(const void *v1, const void *v2)
{
    CUSTOMER *c1, *c2;
    c1 = v1; c2 = v2;
    if (c1->arrival_time == c2->arrival_time)
        return (c1->id - c2->id);
    return (c1->arrival_time - c2->arrival_time);
}
        
int compare_waiting_time(const void *v1, const void *v2)
{
    CUSTOMER *c1, *c2;
    c1 = v1; c2 = v2;
    if (c1->waiting_time == c2->waiting_time)
        return (c1->id - c2->id);
    return (c2->waiting_time - c1->waiting_time);
}

int hh_mm_to_minutes(char *time)
{
    int hh, mm;
    if (strlen(time) != 5 && time[2] != ':')
        return -1;
    sscanf(time, "%d:%d", &hh, &mm);
    if (hh < 0 || hh > 23 || mm < 0 || mm > 59)
        return -1;
    return hh * 60 + mm;
}

int main(int ac, char *av[])
{
    char arrival_time[8];
    int N, i, d, start_time = 0;
    CUSTOMER *customer_list;

    if (ac != 2)
        ERR_MESG("Usage: fcfs <a|b|c>");

    scanf("%d", &N);
    if (NULL == (customer_list = Malloc(N, CUSTOMER)))
        ERR_MESG("fcfs: out of memory\n");
    for (i = 0; i < N; i++) {
        customer_list[i].id = i+1;
        if (2 != scanf("%7s %d", arrival_time, &d))
            ERR_MESG("fcsf: invalid input")
        customer_list[i].arrival_time = hh_mm_to_minutes(arrival_time);
        customer_list[i].duration = d;
    }

    switch (av[1][0]) {
    case 'a':
        for (i = 0; i < N; i++)
            printf("%d\n", customer_list[i].arrival_time);
        break;
    case 'b':
        qsort(customer_list, N, sizeof(CUSTOMER), compare_arrival_time);
        for (i = 0; i < N; i++)
            printf("%d\n", customer_list[i].id);
        break;
    case 'c':
        qsort(customer_list, N, sizeof(CUSTOMER), compare_arrival_time);
        for (i = 0; i < N; i++) {
            customer_list[i].start_time = MAX(start_time, customer_list[i].arrival_time);
            customer_list[i].waiting_time = customer_list[i].start_time -
                customer_list[i].arrival_time;
            start_time = customer_list[i].start_time + customer_list[i].duration;
        }        
        qsort(customer_list, N, sizeof(CUSTOMER), compare_waiting_time);
        for (i = 0; i < N; i++)
            printf("%d %d\n", customer_list[i].id, customer_list[i].waiting_time);        
        break;
    default:
        fprintf(stderr, "Unknown option %s", av[1]);
        exit(1);
    }

    return 0;
}