ants.cpp

 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
	int position;
	int direction;
} ant_t;
 
template<typename V>
int bsearch(V *arr, int sz, int k) {
	int min = 0;
	int max = sz;
	while (max > min) {
		int mid = min + (max - min) / 2;
		int cmp = key(arr[mid]) - k;
 
		if (cmp < 0) {
			min = mid + 1;
		} else if (cmp > 0) {
			max = mid;
		} else {
			return mid;
		}
	}
	return min;
}
 
template<typename V>
void sortInsert(V *arr, int sz, V val) {
	int i = bsearch<V>(arr, sz, key(val));
	while (i <= sz) {
		V tmp1 = arr[i];
		arr[i] = val;
		val = tmp1;
		i++;
	}
}
 
enum {
	LEFT,
	RIGHT
};
 
#define MAKE_STACK(name, sz, value_type) \
	struct { size_t height; value_type *vals; } name; \
	name.height = 0; \
	name.vals = (value_type*) malloc(sizeof(value_type) * sz);
 
#define push_sorted(name, val) \
	(sortInsert(name.vals, name.height, val), name.height++, (void)0)
 
#define push(name, val) \
	(name.vals[name.height++] = (val))
 
#define pop(name) \
	(name.vals[--name.height])
 
#define empty(name) \
	(name.height == 0)
 
 
 
int key(ant_t value) {
	return -value.position;
}
 
#define maximize(name, val) \
	{ if ((val) > name) name = (val); }
 
int main(void) {
	int i;
	int L, A;
 
	while(scanf(" %d %d", &L, &A) == 2) {
		ant_t ant;
		char c;
 
		MAKE_STACK(ants, A, ant_t);
		MAKE_STACK(ants2, A, ant_t);
 
		for (i = 0; i < A; i++) {
			scanf(" %d %c", &ant.position, &c);
			ant.direction = (c == 'R') ? RIGHT : LEFT;
			push_sorted(ants, ant);
			push_sorted(ants2, ant);
		}
 
		int lefts = 0;
		int rights = 0;
 
		int max_right = -1;
		int max_left = -1;
 
 
		while (!empty(ants)) {
			ant = pop(ants);
 
			if (ant.direction == RIGHT) {
				rights++;
 
				int len = L - ant.position;
				if (len > max_right) {
					max_right = len;
				}
			} else {
				lefts++;
 
				if (ant.position > max_left) {
					max_left = ant.position;
				}
			}
		}
 
		for (int i = 0; i < lefts - 1; i++) {
			(void)pop(ants2);
		}
 
		ant_t last_left;
		ant_t last_right;
 
		last_left.position = -1;
		last_right.position = -1;
		if (lefts != 0) {
			last_left = pop(ants2);
		}
		if (rights != 0) {
			last_right = pop(ants2);
		}
 
		if (max_right == max_left) {
			if (last_left.position > last_right.position) {
				int tmp = last_left.position;
				last_left.position = last_right.position;
				last_right.position = tmp;
			}
			printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max_right, last_left.position, last_right.position);
		} else if (max_right > max_left) {
			printf("The last ant will fall down in %d seconds - started at %d.\n", max_right, last_right.position);
		} else {
			printf("The last ant will fall down in %d seconds - started at %d.\n", max_left, last_left.position);
		}
	}
 
	return 0;
}