Source code for submission s816

ants.cpp

  1. #include <stdio.h>
  2. #include <algorithm>
  3.  
  4. #define debug(format,...) fprintf(stderr, format, __VA_ARGS__)
  5. class Ant;
  6. bool operator< (const Ant&, const Ant &);
  7.  
  8. class Ant {
  9. 	public:
  10. 		bool left;
  11. 		int id;
  12. 		int time;
  13. 		friend bool operator< (const Ant&, const Ant &);
  14. /*		bool operator<= (const Ant &ant) {
  15. 			return this->id <= ant.id;
  16. 		}*/
  17. 		void reverse(Ant *ant) {
  18. 			std::swap<int>(this->time, ant->time);
  19. 			this->left = !this->left;
  20. 			ant->left = !ant->left;
  21. 		}
  22. 		bool compare(Ant *ant) {
  23. 			if(!this->left && ant->left) {
  24. 				this->reverse(ant);
  25. 				return true;
  26. 			}
  27. 			return false;
  28. 		}
  29. };
  30.  
  31. bool operator< (const Ant &ant1, const Ant &ant2) {
  32. 	return ant1.id < ant2.id;
  33. }
  34.  
  35.  
  36. int main() {
  37. 	Ant ant[100000];
  38. 	int ants, pos, len, i;
  39. 	int maxTime=-1, maxAnt1=-1, maxAnt2=-1;
  40. 	char dir[3];
  41. 	while(scanf("%d %d", &len, &ants)>0) {
  42. 		for(i=0; i<ants; i++) {
  43. 			scanf("%d %s", &pos, dir);
  44. 			ant[i].id = pos;
  45. 			ant[i].left = (dir[0]=='L');
  46. 			ant[i].time = (ant[i].left ? pos : len-pos);
  47. 			if(maxTime==ant[i].time) {
  48. 				maxAnt2=pos;
  49. 			}else if (maxTime<ant[i].time) {
  50. 				maxTime = ant[i].time;
  51. 				maxAnt1=pos;
  52. 				maxAnt2=-1;
  53. 			}
  54. 		}
  55. 		std::sort(ant+0, ant+ants);
  56. 		for(i=0; i<ants-1;) {
  57. 			if(ant[i].compare(ant+i+1) && i>0) {
  58. 				if(i>0) {
  59. 					i--;
  60. 				} else {
  61. 					i++;
  62. 				}
  63. 			}else {
  64. 				i++;
  65. 			}
  66. 		}
  67.  
  68. 		maxTime = maxAnt2 = -1;
  69. 		for(i=0; i<ants; i++) {
  70. 			if(ant[i].time == maxTime) {
  71. 				maxAnt2 = ant[i].id;
  72. 			}else if (ant[i].time > maxTime) {
  73. 				maxAnt1 = ant[i].id;
  74. 				maxAnt2 = -1;
  75. 				maxTime = ant[i].time;
  76. 			}
  77. 		}
  78. 		if (maxAnt2 == -1) {
  79. 			printf(
  80. 				"The last ant will fall down in %d seconds - started at %d.\n",
  81. 				maxTime, maxAnt1);
  82. 		}else {
  83. 			printf(
  84. 				"The last ant will fall down in %d seconds - started at %d and %d.\n",
  85. 				maxTime, maxAnt1, maxAnt2);
  86. 		}
  87. 	}
  88. 	return 0;
  89. }
  90.  
  91.