ants.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>
#include <math.h>
 
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <algorithm>
 
using namespace std;
 
typedef pair <int, int> PII;
typedef long long int LL;
typedef vector <int> VI;
typedef vector <LL> VLL;
 
#define FOR(i, a, b) for ( int i = a; i < b; ++i )
#define FORD(i, a, b) for ( int i = a-1; i >= 0; --i )
 
#define FILL(x, v, n) for ( int _i = 0; _i < n; ++_i ) x[_i] = v;
 
vector< pair< int, bool> > drevo;
 
bool comp(pair<int, bool> a, pair<int, bool> b)
{
    return a.first < b.first;
}
 
int last (int pos, bool smer){ //smer, ktory ma posledny mravec a index v drevo, na ktorom sa nachadza
 
    if ( pos == -1 )
	return -1;
 
    deque<int> D;
 
    for (unsigned int k = 0; k < drevo.size(); k++)
    {
	int i;
 
	if (smer)
	    i = k;
	else
	    i = drevo.size() - 1 - k;
 
	if ( drevo[i].first == pos ) //skoncil som
	{
	    if ( D.empty() )
		return drevo[i].first;
	    else
		return D.front();
	}
 
	if ( drevo[i].second != smer)
	{
	    D.push_back(drevo[i].first);
	}
	else
	{
	    if ( D.empty() )
		continue;
	    else
	    {
		D.pop_front();
		D.push_back(drevo[i].first);
	    }
	}
    }
 
    abort();
}
 
int main() {
    int L, A;
 
    while (scanf("%d %d", &L, &A) == 2)
    {
	drevo.clear();
 
	int max = -1;
	int i1, i2 = -1;
	bool smer1, smer2 = false;
 
	FOR(i,0,A)
	{
	    int p;
	    char c;
	    scanf("%d %c", &p, &c);
 
	    int d;
	    bool smer;
 
	    if ( c == 'R' )
	    {
		smer = false;
		d = L-p;
	    }
	    else if ( c == 'L' )
	    {
		smer = true;
		d = p;
	    }
 
	    if ( d > max )
	    {
		max = d;
		i1 = p;
		smer1 = smer;
		i2 = -1;
	    }
	    else if ( d == max )
	    {
		i2 = p;
		smer2 = smer;
	    }
 
 
	    drevo.push_back(make_pair(p,smer));
	}
 
	sort(drevo.begin(), drevo.end(), comp);
 
	int p1 = last(i1, smer1);
	int p2 = last(i2, smer2);
 
	printf("The last ant will fall down in %d seconds - started at ", max);
 
	if ( p2 == -1 )
	{
	    printf("%d.\n",p1);
	}
	else
	    printf("%d and %d.\n",min(p1,p2), std::max(p1,p2));
    }
 
	return 0;
 
}