ants.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
// #define INF (int)2e9
#define EPS 1e-9
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
#define MAXN 101000
int l[MAXN];
int r[MAXN];
char ants[MAXN];
int N, D;
bool solve() {
if (scanf("%d%d", &D, &N)<0) return false;
FOR (i, 0, D+2) {
ants[i] = 0;
l[i] = 0;
r[i] = 0;
}
int ret = -1; int rL = -1, rR = -1;
int indexL = 0, indexR = D;
FOR (i, 0, N) {
int a; char c;
scanf("%d %c", &a, &c);
ants[a] = c;
if (c=='L') {
ret = max(ret, a);
if (a==ret) { indexL = a; rL = a; }
}
if (c=='R') {
ret = max(ret, D-a);
if (D-a==ret) { indexR = a; rR = D-a; }
}
}
FOR (i, 0, D+1) {
if (i==0) r[i] = (ants[i]=='R');
else r[i] = r[i-1] + (ants[i]=='R');
//printf("%d ", l[i]);
}
//printf("\n");
for (int i=D; i>=0; i--) {
l[i] = l[i+1] + (ants[i]=='L');
//printf("%d ", r[i]);
}
//printf("\n");
int q=0; int k = 0; int retL, retR;
//printf("%d %d\n", rL, rR);
//printf("%d %d %d %d\n", indexL, indexR, r[indexL], l[indexR]);
if (indexR==D) retL = indexR;
else {
for (k=indexR+1, q=0; q<l[indexR]; k++) {
if (ants[k]!=0) q++;
}
retL = k-1;
}
if (indexL==0) retR = indexL;
else {
for (k=indexL-1, q=0; q<r[indexL]; k--) {
if (ants[k]!=0) q++;
}
retR = k+1;
}
//printf("%d %d\n", retL, retR);
if (rL==rR) {
printf("The last ant will fall down in %d seconds - strarted at %d and %d.\n", rL, min(retL,retR), max(retL,retR));
}
else {
//printf("%d %d %d %d\n", rL, rR, retL, retR);
int opt; int index;
if (rL > rR) { opt = rL; index = retR; }
else { opt = rR; index = retL; }
printf("The last ant will fall down in %d seconds - strarted at %d.\n", opt, index);
}
return true;
}
int main() {
while(solve());
return 0;
}