ants.cpp

#include <stdio.h>
#include <deque>
#include <algorithm>
 
#define MAX(x, y) ((x) >= (y) ? (x) : (y))
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
 
using namespace std;
 
struct Ant {
	int pos;
	char dir;
};
 
bool cmp(const Ant &a, const Ant &b) {
	return a.pos < b.pos;
}
 
int main() {
	int l, count, i;
 
newInstance:
	while (scanf("%d %d\n", &l, &count) != EOF) {
		deque<Ant> q;
 
		int maxDist = -1;
		for (i = 0; i < count; ++i) {
			Ant ant;
			scanf("%d %c\n", &(ant.pos), &(ant.dir));
			q.push_back(ant);
 
			if (ant.dir == 'R')
				maxDist = MAX(ABS(l - ant.pos), maxDist);
			else
				maxDist = MAX(ant.pos, maxDist);
		}
 
		sort(q.begin(), q.end(), cmp);
 
		while (q.size() > 2) {
			Ant a = q.front();
			Ant b = q.back();
			q.pop_front();
 
			if (a.dir == 'R' && q.front().dir == 'L') {
				q.front().dir = 'R';
			} else if (a.dir == 'R' && q.front().dir == 'R') {
				size_t j = 1;
				while (j < q.size() - 1 && q[j].dir == 'R')
					++j;
				if (q[j].dir == 'L') {
					q[j].dir = 'R';
				} else {
					printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, a.pos);
					goto newInstance;
				}
			}
 
			if (q.size() == 2)
				goto twoOrOne;
 
			q.pop_back();
 
			if (b.dir == 'L' && q.back().dir == 'R') {
				q.back().dir = 'L';
			} else if (b.dir == 'L' && q.back().dir == 'L') {
				int j = q.size() - 2;
				while (j > 0 && q[j].dir == 'L')
					--j;
				if (q[j].dir == 'R') {
					q[j].dir = 'L';
				} else {
					printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, b.pos);
					goto newInstance;
				}
			}
		}
 
	twoOrOne:
		if (q.size() == 1) {
			printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, q.front().pos);
		} else if (q.front().dir == 'R' && q.back().dir == 'R') {
			printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, q.front().pos);
		} else if (q.front().dir == 'L' && q.back().dir == 'L') {
			printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, q.back().pos);
		} else {
			int dist1 = q.front().pos;
			int dist2 = l - q.back().pos;
			int diff = dist1 - dist2;
			if (diff > 0)
				printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, q.front().pos);
			else if (diff < 0)
				printf("The last ant will fall down in %d seconds - started at %d.\n", maxDist, q.back().pos);
			else
				printf("The last ant will fall down in %d seconds - started at %d and %d.\n", maxDist, q.front().pos, q.back().pos);
		}
	}
 
	return 0;
}