ants.cpp

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
#define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
 
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////
 
const int MAX = 100000;
int x[MAX];
char d[MAX];
 
int order[MAX];
bool comp(int i, int j)
{
  return x[i] < x[j];
}
 
int main()
{
  int L, A;
  while (scanf("%d%d", &L, &A) == 2)
  {
    REP(i, A) order[i] = i;
    int result = -1, left = 0, right = 0, dir = 0;
    REP(i, A)
    {
      scanf("%d %c", &x[i], &d[i]);
      if (d[i] == 'L')
      {
	if (x[i] > result)
	{
	  dir = 0;
	  result = x[i];
	}
	if (x[i] == result)
	  dir |= 1;
	++left;
      }
      else
      {
	if (L-x[i] > result)
	{
	  dir = 0;
	  result = L-x[i];
	}
	if (L-x[i] == result)
	  dir |= 2;
	++right;
      }
    }
    sort(order, order+A, comp);
 
    printf("The last ant will fall down in %d seconds - started at ", result);
    if (dir == 1)
      printf("%d.\n", x[order[left-1]]);
    else if (dir == 2)
      printf("%d.\n", x[order[A-right]]);
    else
      printf("%d and %d.\n", x[order[left-1]], x[order[A-right]]);
  }
 
  return 0;
}