ants.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
 
 
#define LENGTH 100100
 
using namespace std;
 
struct Ant {
  int pos;
  bool dir;
};
 
 
bool myCompare(const Ant &a, const Ant &b){
  return a.pos < b.pos;
}
 
 
int main ( void )
 {
   int len, ants;
   int i, min, max;
   char tmp;
   int left, right;
 
   while ( scanf ( "%d %d ", &len, &ants ) == 2 )
    {
      vector<Ant> mravenci(ants);
      int pos;
 
      max = -1;
      min = LENGTH * 2;
      left = right = 0;
 
      for ( i = 0; i < ants; i++ )
       {
         scanf ( "%d %c ", &pos, &tmp );
         mravenci[i].pos = pos;
         if ( tmp == 'R' )
          {
            mravenci[i].dir = true;
            right++;
          }
         else
          {
            mravenci[i].dir = false;
            left++;
          } 
       }
 
 
      sort ( mravenci.begin(), mravenci.end(), myCompare );
 
      for ( i = 0; i < ants; i++ ) 
       {
        //cout << mravenci[i].pos << " " << mravenci[i].dir << endl;
         if ( mravenci[i].dir )
          {
            min = i;
            break;
          }
       } 
      for ( i = ants - 1; i >= 0; i-- )  
       {
         if ( !mravenci[i].dir )
          {
            max = i;
            break;
          }  
       }
       //cout << "max " << max << " min " << min << endl;
 
      if ( max == -1 )
       {
         printf ( "The last ant will fall down in %d seconds - started at %d.\n", len - mravenci[min].pos, mravenci[min].pos);
         continue;
       }
      if ( min > LENGTH + 2 )
       {
         printf ( "The last ant will fall down in %d seconds - started at %d.\n", mravenci[max].pos, mravenci[max].pos);
         continue;
       } 
 
      if ( len - mravenci[min].pos == mravenci[max].pos )
       {
          int m1, m2;
          if(mravenci[min + left].pos > mravenci[max - right].pos){
            m1 = mravenci[max - right].pos;
            m2 = mravenci[min + left].pos;
          }
          else{
            m2 = mravenci[max - right].pos;
            m1 = mravenci[min + left].pos;
          }
         printf ( "The last ant will fall down in %d seconds - started at %d and %d.\n", mravenci[max].pos,
            m1, m2 );
       }
       else if(len - mravenci[min].pos > mravenci[max].pos){
          printf ( "The last ant will fall down in %d seconds - started at %d.\n", len - mravenci[min].pos, mravenci[min + left].pos);
       }
       else{
        printf ( "The last ant will fall down in %d seconds - started at %d.\n", mravenci[max].pos, mravenci[max - right].pos);
       }
    }
   return 0;
 }