Source code for submission s1060

ants.cpp

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cassert>
  4. #include <vector>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. #define LEFT true
  10. #define RIGHT false
  11.  
  12. struct ant
  13. {
  14. ant(){};
  15. ant(bool _dir, int _pos): dir(_dir),pos(_pos)
  16. { }
  17. bool operator<(const ant& other) const
  18. {
  19. return pos < other.pos;
  20. }
  21.  
  22. bool dir;
  23. int pos;
  24. };
  25.  
  26. int whois(int a, vector<ant> &ants, int length)
  27. {
  28. assert(a<ants.size());
  29. bool dir = ants[a].dir;
  30. int current = ants[a].pos;
  31. int dist = dir==LEFT? current: length-current;
  32. int lb = dir==LEFT? 0: a+1;
  33. int rb = dir==LEFT? a-1: ants.size()-1;
  34. while(lb<=rb && lb>=0 && rb<ants.size())
  35. {
  36. if(dir==LEFT)
  37. {
  38. bool found=false;
  39. for(int i=lb; i<=rb; ++i)
  40. {
  41. if(ants[i].dir==RIGHT)
  42. {
  43. current=ants[i].pos;
  44. lb = i+1;
  45. dir = !dir;
  46. found=true;
  47. break;
  48. }
  49. }
  50. if(!found) break;
  51. }
  52. else if(dir==RIGHT)
  53. {
  54. bool found=false;
  55. for(int i=rb; i>=lb; --i)
  56. {
  57. if(ants[i].dir==LEFT)
  58. {
  59. current=ants[i].pos;
  60. rb = i-1;
  61. dir = !dir;
  62. found=true;
  63. break;
  64. }
  65. }
  66. if(!found) break;
  67. }
  68. }
  69. return current;
  70. }
  71.  
  72. int main()
  73. {
  74. while(true)
  75. {
  76. int length, antCount;
  77. cin >> length >> antCount;
  78. if(!cin) break;
  79. vector<ant> ants;
  80. for(int i=0; i<antCount; ++i)
  81. {
  82. int pos;
  83. string dir;
  84. cin >> pos >> dir;
  85. if(dir=="L")
  86. {
  87. ants.push_back(ant(LEFT, pos));
  88.  
  89. }
  90. else if(dir=="R")
  91. {
  92. ants.push_back(ant(RIGHT, pos));
  93. }
  94. }
  95.  
  96. std::sort(ants.begin(), ants.end());
  97.  
  98.  
  99. int ld=0;
  100. int rd=0;
  101. int ri=-1;
  102. for(vector<ant>::iterator a=ants.begin(); a!=ants.end(); ++a)
  103. {
  104. if(a->dir==RIGHT)
  105. {
  106. ri=a-ants.begin();
  107. rd = length-a->pos;
  108. break;
  109. }
  110. }
  111.  
  112. int li=-1;
  113. for(vector<ant>::iterator a=ants.end()-1; a!=ants.begin()-1; --a)
  114. {
  115. if(a->dir==LEFT)
  116. {
  117. li=a-ants.begin();
  118. ld= a->pos;
  119. break;
  120. }
  121. }
  122.  
  123. if(li==-1)
  124. {
  125. cout << "The last ant will fall down in "<<rd<<" seconds - started at "<<whois(ri,ants, length)<<"."<<endl;
  126. } else if(ri==-1)
  127. {
  128. cout << "The last ant will fall down in "<<ld<<" seconds - started at "<<whois(li,ants,length)<<"."<<endl;
  129. }
  130. else if(ld<rd)
  131. {
  132. cout << "The last ant will fall down in "<<rd<<" seconds - started at "<<whois(ri,ants, length)<<"."<<endl;
  133. }
  134. else if(ld>rd)
  135. {
  136. cout << "The last ant will fall down in "<<ld<<" seconds - started at "<<whois(li,ants,length)<<"."<<endl;
  137. }
  138. else
  139. {
  140. int a = whois(li,ants,length);
  141. int b = whois(ri,ants,length);
  142. cout << "The last ant will fall down in "<<ld<<" seconds - started at "<<std::min(a,b)<<
  143. " and "<<std::max(a,b)<<"."<<endl;
  144.  
  145. }
  146. }
  147. return 0;
  148. }
  149.  
  150.