Source code for submission s798

ants.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <algorithm>
  4.  
  5. #define MAXN 200000
  6.  
  7. using namespace std;
  8.  
  9. typedef struct ANT
  10. {
  11. 	int i;
  12. 	char d;
  13.  
  14. 	ANT() {}
  15. 	ANT(int i, char d): i(i), d(d) {}
  16.  
  17. 	bool operator < (const ANT& a) const {return i < a.i;}
  18. }
  19. ANT;
  20.  
  21. ANT Ant[MAXN];
  22.  
  23. int min(int a, int b)
  24. {
  25. 	return (a < b) ? a : b;
  26. }
  27.  
  28. int max(int a, int b)
  29. {
  30. 	return (a > b) ? a : b;
  31. }
  32.  
  33. int main()
  34. {
  35. 	char c;
  36. 	int l, n;
  37.  
  38. 	while(scanf("%d%d", &l, &n) > 0)
  39. 	{
  40. 		for(int i = 0; i < n; i++)
  41. 		{
  42. 			scanf("%d%c%c", &(Ant[i].i), &c, &(Ant[i].d));
  43. 		}
  44.  
  45. 		sort(Ant, Ant + n);
  46.  
  47. 		/*for(int i = 0; i < n; i++)
  48. 		{
  49. 			printf("%d %c\n", Ant[i].i, Ant[i].d);
  50. 		}*/
  51.  
  52. 		int right = -1, left = -1, nRight = 0, nLeft = 0, rslRight = -1, rslLeft = -1;
  53. 		for(int i = 0; i < n; i++)
  54. 		{
  55. 			if(right == -1)
  56. 			{
  57. 				if(Ant[i].d == 'R')
  58. 				{
  59. 					right = i;
  60. 				}
  61. 			}
  62. 			else if(Ant[i].d == 'L')
  63. 			{
  64. 				nRight++;
  65. 			}
  66. 		}
  67.  
  68. 		for(int i = n - 1; i >= 0; i--)
  69. 		{
  70. 			if(left == -1)
  71. 			{
  72. 				if(Ant[i].d == 'L')
  73. 				{
  74. 					left = i;
  75. 				}
  76. 			}
  77. 			else if(Ant[i].d == 'R')
  78. 			{
  79. 				nLeft++;
  80. 			}
  81. 		}
  82.  
  83. 		int rr = -1, ll = -1;
  84. 		if(right != -1)
  85. 		{
  86. 			rr = l - Ant[right].i;
  87. 			rslRight = right + nRight;
  88. 		}
  89.  
  90. 		if(left != -1)
  91. 		{
  92. 			ll = Ant[left].i;
  93. 			rslLeft = left - nLeft;
  94. 		}
  95.  
  96. 		if(rr == ll)
  97. 		{
  98. 			printf("The last ant will fall down in %d seconds - started at %d and %d.\n", ll,
  99. 			       min(Ant[rslLeft].i, Ant[rslRight].i),
  100. 			       max(Ant[rslLeft].i, Ant[rslRight].i));
  101. 		}
  102. 		else
  103. 		{
  104. 			if(rr > ll)
  105. 			{
  106. 				ll = rr;
  107. 				rslLeft = rslRight;
  108. 			}
  109.  
  110. 			printf("The last ant will fall down in %d seconds - started at %d.\n", ll, Ant[rslLeft].i);
  111. 		}
  112. 	}
  113.  
  114. 	return 0;
  115. }
  116.