ants.cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define PB push_back
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define fi first
#define se second
#define SIZE(s) (int) (s).size()
#define INF 987654321
#define ll long long
//----------------------
int N;
int dlzka;
vector< pair<int, char> > V;
vector< pair<int, char> > V2;
int find(double val)
{
FOR(i,0,SIZE(V2)-1)
if (V2[i].fi >= val) return i;
return -1;
}
void solve2(int lavy, int pravy,int kolko)
{
int pozL = V2[lavy].fi;
int pozR = V2[pravy].fi;
if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR);
else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
}
void solve1(int lavy, int pravy,int kolko)
{
if (lavy == -1)
{
int pozR = V[pravy].fi;
printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
}
else if (pravy == -1)
{
int pozL = V[lavy].fi;
printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
}
else
{
int pozL = V[lavy].fi;
int pozR = V[pravy].fi;
if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR);
else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
}
}
int main()
{
char z;
int poz;
while(scanf("%d %d",&dlzka,&N)==2)
{
V.clear();
V2.clear();
int kolko=-1;
int lavy = -1;
int pravy = -1;
bool existuje = false;
FOR(i,0,N-1)
{
scanf("%d %c",&poz,&z);
//cout << poz << " " << z << endl;
if (z == 'L') kolko = max(poz,kolko);
else kolko = max(kolko,dlzka-poz);
V.PB(MP(poz,z));
}
sort(V.begin(),V.end());
FOR(i,0,N-1)
{
if (i>0 && V[i-1].se == 'L' && V[i].se == 'R') existuje = true;
if (V[i].se == 'L') lavy = i;
if (pravy == -1 && V[i].se == 'R') pravy = i;
}
// cout << lavy << endl;
FOR(i,0,N-1)
{
if (pravy == -1 && V[i].se == 'L')
{
}
else
V2.PB(V[i]);
if (lavy > 0 && lavy == i) break;
}
if (existuje)
{
int pozL = V2[0].fi;
int pozR = V2[SIZE(V2)-1].fi;
// cout << pozL << " " << pozR << endl;
double stred = (pozL+pozR) / 2.0;
int idx1 = find(stred);
// cout << stred << " " << idx1 << endl;
int idx2 = idx1-1;
solve2(idx2,idx1,kolko);
}
else
{
solve1(lavy,pravy,kolko);
}
}
return 0;
}