Source code for submission s852

ants.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Ant
  8. {
  9. 	int pos;
  10. 	char dir;
  11. 	int rotations;
  12. /*	Ant(int pos, char dir)
  13. 	{
  14. 		this->pos = pos;
  15. 		this->dir = dir;
  16. 	}*/
  17. };
  18.  
  19. int compareAnt(const void* a, const void* b)
  20. {
  21. 	return ((Ant*) a)->pos - ((Ant*) b)->pos;
  22. }
  23.  
  24. int main()
  25. {
  26. 	int length, count;
  27.  
  28. 	while (true) {
  29.  
  30. 		if (scanf("%d %d\n", &length, &count) != 2) break;
  31.  
  32. 		Ant* ants = new Ant[100000];
  33. 		int antLen = 0;
  34.  
  35. 		for (int i = 0; i < count; i++) {
  36. 			scanf("%d %c\n", &ants[antLen].pos, &ants[antLen].dir);
  37. 			ants[antLen].rotations = 0;
  38. 			antLen++;
  39. 		}
  40.  
  41. 		qsort(ants, antLen, sizeof(Ant), compareAnt);
  42.  
  43.  
  44.  
  45. 		int l = 0;
  46. 		int r = 0;
  47. 		for (int i = 0; i < antLen; i++) {
  48. 			ants[i].rotations = r;		
  49. 			if (ants[i].dir == 'R') r++;
  50. 		}
  51.  
  52. 		int minLR;
  53. 		char minDir;
  54. 		int maxRotations = 0;
  55. 		for (int i = antLen - 1; i >= 0; i--) {
  56. 			r = ants[i].rotations;
  57. 			if (l < r) {
  58. 				minLR = l;
  59. 				minDir = 'L';
  60. 			} else if (l > r) {
  61. 				minLR = r;
  62. 				minDir = 'R';
  63. 			} else {
  64. 				minLR = l;
  65. 				minDir = '?';
  66. 			}
  67.  
  68. 			ants[i].rotations = 2 * minLR + (int) (ants[i].dir == minDir);
  69. 			maxRotations = max(maxRotations, ants[i].rotations);
  70. 			if (ants[i].dir == 'L') l++;
  71. 		}
  72.  
  73. 		int results[2];
  74. 		int resultsCount = 0;
  75. 		int maxDistance = 0;
  76. 		int maxDistance2 = 0;
  77. 		for (int i = 0; i < antLen; i++) {
  78. 	//		int dist = abs(ants[i].pos - length);
  79.  
  80. 			int dist;
  81. 			if (ants[i].dir == 'L') {
  82. 				dist = ants[i].pos;
  83. 			} else {
  84. 				dist = length - ants[i].pos;
  85. 			}
  86.  
  87. 			maxDistance2 = max(maxDistance2, dist);
  88.  
  89. 			if (ants[i].rotations == maxRotations) {
  90. 				if (dist > maxDistance) {
  91. 					maxDistance = dist;
  92. 					resultsCount = 0;
  93. 				}
  94. 				if (resultsCount < 2) {
  95. 					results[resultsCount++] = ants[i].pos;
  96. 				}
  97. 			}
  98. 		}
  99.  
  100. 		printf("The last ant will fall down in %d seconds - started at ", maxDistance2);
  101. 		if (resultsCount == 2) {
  102. 			printf("%d and %d.\n", results[0], results[1]);
  103. 		} else {
  104. 			printf("%d.\n", results[0]);
  105. 		}
  106. 	}
  107.  
  108.  
  109. 	return 0;
  110. }
  111.