Source code for submission s1058

ants.cpp

  1. //
  2. // File:   ants.cc
  3. // Author: cteam053
  4. //
  5. // Created on October 27, 2012, 1:06 PM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <climits>
  12. #include <iostream>
  13.  
  14. using namespace std;
  15.  
  16. int rightAr[100000];
  17. int leftAr[100000];
  18. char ants[100000];
  19. int lCnt = 0;
  20. int rCnt = 0;
  21. int L, A;
  22. int pos;
  23. int maxVal;
  24. int minVal;
  25. int minCnt;
  26. int minAnts[100000];
  27. int r, l;
  28.  
  29. int main(int argc, char** argv) {
  30.  
  31.     char c, space;
  32.     int len;
  33.     int tmp;
  34.     while(scanf("%d%d", &L, &A) == 2){
  35.         lCnt = 0;
  36.         rCnt = 0;
  37.         minVal = INT_MAX;
  38.         maxVal = -1;
  39.         r = 0;
  40.         l = 0;
  41.         for(int i = 0; i < L; i++){
  42.             ants[i] = 'A';
  43.             rightAr[i] = 0;
  44.             leftAr[i] = 0;
  45.         }
  46.         for(int i = 0; i < A; i++){
  47.             scanf("%d%c%c", &pos, &space, &c);
  48.             if(c == 'R'){
  49.                 len = L - pos;
  50.             } else {
  51.                 len = pos;
  52.             }
  53.             maxVal = (maxVal < len) ? len : maxVal;
  54.             ants[pos] = c;
  55.         }
  56.         for(int i = 0; i < L; i++){
  57.             if(ants[i] == 'R'){
  58.                 if(i < L - 1)
  59.                     rightAr[i+1] = ++rCnt;
  60.             }
  61.         }
  62.         for(int i = L -1; i > 0; i--){
  63.             if(ants[i] == 'L'){
  64.                 leftAr[i-1] = ++lCnt;
  65.             }
  66.         }
  67.  
  68.         for(int i = 0; i < L; i++){
  69.             if(rightAr[i] < r){
  70.                 rightAr[i] = r;
  71.             } else if(rightAr[i] > r){
  72.                 r = rightAr[i];
  73.             }
  74.         }
  75.         for(int i = L -1; i >= 0; i--){
  76.             if(leftAr[i] < l){
  77.                 leftAr[i] = l;
  78.             } else if(leftAr[i] > l){
  79.                 l = leftAr[i];
  80.             }
  81.         }
  82.         for(int i = 0; i < L; i++){
  83.             if(ants[i] != 'A'){
  84.                 tmp = abs(rightAr[i] - leftAr[i]);
  85.                 if(tmp < minVal){
  86.                     minVal = tmp;
  87.                     minCnt = 0;
  88.                     minAnts[minCnt++] = i;
  89.                 } else if(tmp == minVal){
  90.                     minAnts[minCnt++] = i;
  91.                 }
  92.             }
  93.         }
  94.         printf("The last ant will fall down in %d  seconds - started at ", maxVal);
  95.         for(int i = 0; i < minCnt; i++){
  96.             printf("%d", minAnts[i]);
  97.             if(i == minCnt - 1){
  98.                 printf(".\n");
  99.             } else {
  100.                 printf(" and ");
  101.             }
  102.         }
  103.     }
  104.  
  105.     return (0);
  106. }
  107.  
  108.