Source code for submission s1338

ants.cpp

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef unsigned long int ulint;
  9.  
  10. struct ant
  11. {
  12. ant() {}
  13. ant(int start, int pos, int dir) :
  14. start(start), pos(pos), dir(dir) {}
  15.  
  16. int start;
  17. int pos;
  18. int dir;
  19. int steps;
  20. };
  21.  
  22. static bool ant_at[2][100100];
  23.  
  24. static ant ants[100100];
  25.  
  26. static ulint L;
  27. static ulint A;
  28.  
  29. int main()
  30. {
  31. char dir;
  32. ulint pos;
  33. while (scanf("%lu %lu", &L, &A) != EOF)
  34. {
  35. memset(ant_at, false, sizeof(ant_at));
  36. for (uint a = 0; a < A; ++a)
  37. {
  38. scanf("%lu %c", &pos, &dir);
  39. ant_at[(dir == 'L') ? 0 : 1][pos] = true;
  40. ants[a] = ant(pos, pos, (dir == 'L') ? -1 : 1);
  41. }
  42.  
  43. vector<int> fallen;
  44. int steps = 0;
  45. int end_steps;
  46. int A_curr = A;
  47. while (A_curr > 0)
  48. {
  49. fallen.clear();
  50. for (uint a = 0; a < A; ++a)
  51. {
  52.  
  53. if (ants[a].pos < 0 || ants[a].pos >L)
  54. {
  55. continue;
  56. }
  57.  
  58. int npos = ants[a].pos + ants[a].dir;
  59. int cpos1 = npos;
  60. int cpos2 = npos + ants[a].dir;
  61. int my_dir = (ants[a].dir == -1) ? 0 : 1;
  62. int opp_dir = (ants[a].dir == -1) ? 1 : 0;
  63.  
  64. if (cpos1 >= 0 && cpos1 <= L && ant_at[opp_dir][cpos1])
  65. {
  66. ants[a].dir *= -1;
  67. }
  68. else if (cpos2 >= 0 && cpos2 <= L && ant_at[opp_dir][cpos2])
  69. {
  70. ants[a].pos += ants[a].dir;
  71. ants[a].dir *= -1;
  72.  
  73. if (ants[a].pos < 0 || ants[a].pos > L)
  74. {
  75. fallen.push_back(ants[a].start);
  76. //printf("%d %d\n",steps,ants[a].start);
  77. --A_curr;
  78. }
  79. }
  80. else
  81. {
  82. ants[a].pos += ants[a].dir;
  83.  
  84. if (ants[a].pos < 0 || ants[a].pos > L)
  85. {
  86. /*
  87.   if (fallen == 0)
  88.   {
  89.   fallen[0] = ants[a].start;
  90.   }
  91.   else if (fallen == 1)
  92.   {
  93.   fallen[1] = ants[a].start;
  94.   }
  95.   else
  96.   {
  97.   fallen[0] = fallen[1];
  98.   fallen[1] = ants[a].start;
  99.   }
  100.   */
  101. fallen.push_back(ants[a].start);
  102. //printf("%d %d\n",steps, ants[a].start);
  103. --A_curr;
  104. }
  105. }
  106.  
  107. if (A_curr == 0)
  108. {
  109. //printf("%d\n", fallen.size());
  110. if (fallen.size() == 1)
  111. {
  112. printf("The last ant will fall down in %d seconds - started at %d.\n", steps, fallen[fallen.size() - 1]);
  113. }
  114. else
  115. {
  116. printf("The last ant will fall down in %d seconds - started at %d and %d.\n", steps, min(fallen[0], fallen[1]), max(fallen[0], fallen[1]));
  117. }
  118. break;
  119. }
  120. }
  121. ++steps;
  122.  
  123. for (uint l = 0; l <= L; ++l)
  124. {
  125. ant_at[0][l] = false;
  126. ant_at[1][l] = false;
  127. }
  128. for (uint a = 0; a < A; ++a)
  129. {
  130. if (ants[a].dir == -1)
  131. {
  132. ant_at[0][ants[a].pos] = true;
  133. }
  134. else
  135. {
  136. ant_at[1][ants[a].pos] = true;
  137. }
  138. }
  139.  
  140. /*
  141.   for (uint a = 0; a < A; ++a)
  142.   {
  143.   printf("%d ", ants[a].pos);
  144.   }
  145.  
  146.   printf("\n");
  147.  
  148.   for (uint a = 0; a < A; ++a)
  149.   {
  150.   printf("%d ", ants[a].dir);
  151.   }
  152.   printf("\n");
  153.   for (uint l = 0; l < L; ++l)
  154.   {
  155.   printf("%d ", ant_at[0][l]);
  156.   }
  157.   printf("\n");
  158.   for (uint l = 0; l < L; ++l)
  159.   {
  160.   printf("%d ", ant_at[1][l]);
  161.   }
  162.   printf("\n");
  163.  
  164.   //char c;
  165.   getchar();
  166.   */
  167. }
  168. }
  169. }