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.