ants.cpp

#include <stdio.h>
#include <algorithm>
 
struct Ant{
 int pos;
 char dir;
};
 
bool comparer(Ant const & a, Ant const & b)
{
	return a.pos<b.pos;
}
 
int main() {
 
	Ant * ants(0);
	int L;
	int A;
 
	// main cycle
	while( scanf( "%d %d\n", &L, &A ) == 2 ) {
		delete[] ants;
		ants = new Ant[A];
 
		int leftValueStart(-1);
		int rightValueStart(-1);
		int leftValueBest(-1);
		int rightValueBest(-1);		
 
		// read ants
		Ant * afterEnd(ants+A);
		for( Ant * cur(ants); cur < afterEnd; ++cur )
			scanf( "%d %c\n", &(cur->pos), &(cur->dir) );
 
		// sort array
		std::sort(ants,ants+A,comparer);
 
		// find leftWalkerBest
		int opositeWalkers(0);
		for( Ant * cur(ants); cur < afterEnd; ++cur ) {
			if( cur->dir == 'R' ) 
				++opositeWalkers;
 
			else
			{
				leftValueBest = cur->pos;
				leftValueStart = (cur-opositeWalkers)->pos;
 
			}
		}
 
 
		// find rightWalkerBest
		opositeWalkers = 0;
		for( Ant * cur(ants+A-1); cur >= ants ; --cur ) {
			//printf( "\n\n%d %c\n", (cur->pos), (cur->dir) );
			if( cur->dir == 'L' ) 
			{
				++opositeWalkers;
				//printf("\nOV%d",opositeWalkers);
			}
			else
			{
				rightValueBest = L - cur->pos;
				rightValueStart = (cur+opositeWalkers)->pos;
				//printf("\nCHG%d %d",leftValueBest,leftValueStart);
			}
		}
 
		if( leftValueBest < rightValueBest ) {
			printf( "The last ant will fall down in %d seconds - started at %d\n", rightValueBest, rightValueStart );
		} else if ( leftValueBest > rightValueBest ) {
			printf( "The last ant will fall down in %d seconds - started at %d\n", leftValueBest, leftValueStart );
		} else {
			printf( "The last ant will fall down in %d seconds - started at %d and %d\n", leftValueBest, leftValueStart, rightValueStart );
		}
	}
 
	return 0;
}