sablona.cc

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <sstream>
 
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
 
using namespace std;
 
#define X first
#define Y second
#define MP make_pair
#define PB push_back
#define SZ size
 
struct Dvojice {
   int zac;
   char smer;
};
 
int compare (const void *a, const void *b) {
   struct Dvojice a1 = *(struct Dvojice*)a;
   struct Dvojice b1 = *(struct Dvojice*)b;
   return (a1.zac-b1.zac);
}
 
int main(void)
{
   int a, b, c, d, f, g, aa, i, ii, akt, akt2, j, k, ok2, ok, pom1, pom2, cas1, cas2, max;
   char e;
   struct Dvojice mrv[100005];
 
   while (scanf("%d %d", &a, &b) > 0) {
      max = 0;
      for (i = 0; i < b; i++) {
         scanf("%d %c\n", &c, &e);
         mrv[i].zac = c;
         mrv[i].smer = e;
         if (e == 'R') {
            if (a - c > max)
               max = a - c;
         } else {
            if (c > max)
               max = c;
         }
      }
      qsort(mrv, b, sizeof(struct Dvojice), compare);
      d = 0;
      f = b - 1;
      ok2 = 1;
      while(d < f && ok2 == 1) {
         ok = 0;
         pom1 = d + 1;
         pom2 = f - 1;
         while (ok == 0) {
            if (mrv[pom1].smer != mrv[d].smer) {
               ok = 1;
            } else {
               pom1++;
            }
            if (pom1 > f) {
               ok = 1;
               pom1 = -1;
            }
         }
         ok = 0;
         while (ok == 0) {
            if (mrv[pom2].smer != mrv[f].smer) {
               ok = 1;
            } else {
               pom2++;
            }
            if (pom2 < d) {
               ok = 1;
               pom2 = -1;
            }
         }
         if (pom1 != -1) {
            cas1 = mrv[pom1].zac - mrv[d].zac;
         }
         if (pom2 != -1) {
            cas2 = mrv[f].zac - mrv[pom2].zac;
         }
         if (pom1 != -1) {
            if (cas1 == cas2) {
               if (mrv[pom2].smer == 'R')
                  mrv[pom2].smer = 'L';
               else
                  mrv[pom2].smer = 'R';
               f--;
               if (mrv[pom1].smer == 'R')
                  mrv[pom1].smer = 'L';
               else
                  mrv[pom1].smer = 'R';
               d++;
            } else if (cas1 > cas2) {
               if (mrv[pom2].smer == 'R')
                  mrv[pom2].smer = 'L';
               else
                  mrv[pom2].smer = 'R';
               f--;  
            } else {
               if (mrv[pom1].smer == 'R')
                  mrv[pom1].smer = 'L';
               else
                  mrv[pom1].smer = 'R';
               d++;  
            }
         } else {
            ok2 = 0;
         }
         //printf("%d %d\n", d, f);
      }
      if (ok2 == 0) {
         if (mrv[d].smer == 'L')
            printf("The last ant will fall down in %d seconds - started at %d.\n", max, mrv[f].zac);
         else
            printf("The last ant will fall down in %d seconds - started at %d.\n", max, mrv[d].zac);
      } else {
         if (a - mrv[d].zac > mrv[f].zac)
            printf("The last ant will fall down in %d seconds - started at %d.\n", max, mrv[d].zac);
         else if (a - mrv[d].zac > mrv[f].zac)
            printf("The last ant will fall down in %d seconds - started at %d.\n", max, mrv[f].zac);
         else
            printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max, mrv[f].zac, mrv[d].zac);
      }
   }
 
   return 0;
}