Source code for submission s838

a.cpp

  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <string>
  7. #include <cstring>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <utility>
  11. #include <stack>
  12. #include <vector>
  13. #include <queue>
  14. #include <deque>
  15. #include <set>
  16. #include <map>
  17. #include <list>
  18.  
  19. #define SIZEOF(a) (sizeof(a)/sizeof(a[0]))
  20. #define FILL(a,b) fill(a,a+SIZEOF(a),b)
  21. #define FOR(a,b,c) for(int a=b;a<=c;a++)
  22. #define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++)
  23. #define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++)
  24. #define GETI(a) scanf("%d ", &a);
  25. #define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; }
  26.  
  27. using namespace std;
  28.  
  29.  
  30. struct ant {
  31. int id;
  32. int pos;
  33. int dir; // 1 for right, -1 for left
  34. ant(int id, int pos, int dir) : id(id), pos(pos), dir(dir) {}
  35. };
  36.  
  37. bool operator<(const ant& a, const ant& b) {
  38. return a.pos < b.pos;
  39. }
  40.  
  41. void answer(int id, int time)
  42. {
  43. cout << "The last ant will fall down in " << time << " seconds - started at " << id << "." << endl;
  44. }
  45.  
  46. void answer(int id, int id2, int time)
  47. {
  48. cout << "The last ant will fall down in " << time << " seconds - started at " << id << " and " << id2 << "." << endl;
  49. }
  50.  
  51.  
  52. void print_ants(deque<ant> ants)
  53. {
  54. FOREACH(a,ants) {
  55. cerr << a->id << "(pos " << a->pos << ", dir " << a->dir << "), ";
  56. }
  57. }
  58.  
  59.  
  60. int main(void)
  61. {
  62.  
  63. int L, A;
  64. cin >> L >> A;
  65. while (!feof(stdin)) {
  66. L *= 2;
  67. // cerr << "read " << L << " " << A << endl;
  68.  
  69. deque<ant> ants;
  70. vector<ant> antsv;
  71. FOR(i,1,A) {
  72. int pos;
  73. char dir;
  74. cin >> pos >> dir;
  75. antsv.push_back(ant(pos, pos*2, (dir == 'L' ? -1 : 1)));
  76. }
  77.  
  78. // sort by pos
  79. sort(antsv.begin(), antsv.end());
  80.  
  81. FOREACH(a, antsv) {
  82. ants.push_back(*a);
  83. }
  84. // print_ants(ants);
  85. // cerr << endl;
  86.  
  87. FOR(time,0,L+3) {
  88. // cerr << "AT " << time << ": ";
  89. // print_ants(ants);
  90. // cerr << endl;
  91.  
  92.  
  93. // let them walk
  94. FOREACH(i,ants) {
  95. // collsions?
  96. deque<ant>::iterator nb = i+1;
  97. if (nb != ants.end() && nb->pos == i->pos) {
  98. i->dir *= -1;
  99. nb->dir *= -1;
  100. if (i->pos == nb->pos) {
  101. i->pos += i->dir;
  102. nb->pos += nb->dir;
  103. }
  104. i++;
  105. }
  106. else {
  107. i->pos += i->dir;
  108. }
  109. }
  110.  
  111. // let them fall
  112. int fallenId = -1;
  113. if (ants.front().pos == -1) {
  114. fallenId = ants.front().id;
  115. if (ants.size() == 1) {
  116. answer(fallenId, time/2);
  117. break;
  118. }
  119. ants.pop_front();
  120. }
  121. if (ants.back().pos == L+1) {
  122. if (ants.size() == 1) {
  123. // the last ant!
  124. int id = ants.back().id;
  125. if (fallenId == -1) {
  126. // id is the only one
  127. answer(id, time/2);
  128. }
  129. else {
  130. // they both fell down now
  131. answer(min(fallenId, id), max(fallenId, id), time/2);
  132. }
  133. break; // we won!
  134. }
  135.  
  136. ants.pop_back();
  137. }
  138. }
  139.  
  140.  
  141.  
  142. cin >> L >> A;
  143. }
  144.  
  145.  
  146.  
  147. return 0;
  148. }
  149.