ants.cpp

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
inline bool is_inside(pair<int, int> place, int ants){
	return place.first >= 0 && place.first < ants && place.second < ants && place.second >= 0;
}
 
inline bool have_conflict(pair<int, char> first, pair<int, char> second){
	return first.second == 'R' && second.second == 'L';
}
 
inline void flip(pair<int, int> positions, vector<pair<int, char> >& vect){
	int x, y;
	x = positions.first;
	y = positions.second;
	vect[x].second = 'L';
	vect[y].second = 'R';
}
 
inline int maximum(int first, int second){
	return (first < second) ? second : first;
}
 
 
int main() {
	int len, ants, place, distance, max, number;
	char face;
	while(scanf("%d %d",  &len, &ants) == 2) {
		vector<pair<int, char> > vect;
		vector<int> position(2);
		distance = -1;
		number = 0;
		max = -1;
		for (int i = 0; i < ants; i++) {
			scanf("%d %c", &place, &face);
			vect.push_back(make_pair(place, face));
			distance = (face == 'L') ? place : (len-place);
			if (distance > max) {
				number = 1;
				max = distance;
			} else if (distance == max) {
				number = 2;
			}
		}
		sort(vect.begin(), vect.end());
		pair<int, int> current;
		stack<pair<int, int> > stack;
		stack.push(make_pair(0,1));
		while (!stack.empty()) {
			current = stack.top();
			stack.pop();
			if (is_inside(current, ants)){
				if (have_conflict(vect[current.first], vect[current.second])){
					flip(current, vect);
					stack.push(make_pair(current.second, current.second+1));
					stack.push(make_pair(current.first - 1, current.first));
				} else {
					stack.push(make_pair(current.second, current.second + 1));
				}
			}
		}
 
		int ii = 0;
		while (ii < ants && vect[ii].second == 'L'){
			ii++;
		}
		if (ii == 0){
			position[0] = vect[0].first;
		} else if (ii == ants) {
			position[0] = vect[ants-1].first;
		} else {
			if (number == 2){
				position[0] = vect[ii-1].first;
				position[1] = vect[ii].first;
			} else {
				position[0] = maximum(vect[ii].first, vect[ii-1].first);
			}
		}
 
 
		if (number == 1){
			printf("The last ant will fall down in %d seconds - started at %d.\n", max, position[0]);
		} else {
			printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max, position[0], position[1]);
		}
 
	}
	return 0;
}