Source code for submission s880

ants.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cctype>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <algorithm>
  9. #include <deque>
  10. #include <list>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <vector>
  16.  
  17. #define FOR(I,A,B)	for(int I = (A); I < (B); ++I)
  18.  
  19. // #define INF (int)2e9
  20. #define EPS 1e-9
  21. #define PI 3.14159265358979
  22.  
  23. using namespace std;
  24.  
  25. typedef pair<int, int> ii;
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28.  
  29. #define MAXN 101000
  30.  
  31. int l[MAXN];
  32. int r[MAXN];
  33. char ants[MAXN];
  34. int N, D;
  35.  
  36. bool solve() {
  37. 		if (scanf("%d%d", &D, &N)<0) return false;
  38. 		FOR (i, 0, D+2) {
  39. 			ants[i] = 0;
  40. 			l[i] = 0;
  41. 			r[i] = 0;
  42. 		}
  43. 		int ret = -1; int rL = -1, rR = -1;
  44. 		int indexL = 0, indexR = D;
  45. 		FOR (i, 0, N) {
  46. 			int a; char c;
  47. 			scanf("%d %c", &a, &c);
  48. 			ants[a] = c;
  49. 			if (c=='L') {
  50. 				ret = max(ret, a);
  51. 				if (a==ret) { indexL = a; rL = a; }
  52. 			}
  53. 			if (c=='R') {
  54. 				ret = max(ret, D-a);
  55. 				if (D-a==ret) { indexR = a; rR = D-a; }
  56. 			}
  57. 		}
  58. 		FOR (i, 0, D+1) {
  59. 			if (i==0) r[i] = (ants[i]=='R');
  60. 			else r[i] = r[i-1] + (ants[i]=='R');
  61. 			//printf("%d ", l[i]);
  62. 		}
  63. 		//printf("\n");
  64. 		for (int i=D; i>=0; i--) {
  65. 			l[i] = l[i+1] + (ants[i]=='L');
  66. 			//printf("%d ", r[i]);
  67. 		}
  68. 		//printf("\n");
  69. 		int q=0; int k = 0; int retL, retR;
  70. 		//printf("%d %d\n", rL, rR);
  71. 		//printf("%d %d %d %d\n", indexL, indexR, r[indexL], l[indexR]);
  72. 		if (indexR==D) retL = indexR;
  73. 		else {
  74. 			for (k=indexR+1, q=0; q<l[indexR]; k++) {
  75. 				if (ants[k]!=0) q++;
  76. 			}
  77. 			retL = k-1;
  78. 		}
  79. 		if (indexL==0) retR = indexL;
  80. 		else {
  81. 			for (k=indexL-1, q=0; q<r[indexL]; k--) {
  82. 				if (ants[k]!=0) q++;
  83. 			}
  84. 			retR = k+1;
  85. 		}
  86. 		//printf("%d %d\n", retL, retR);
  87. 		if (rL==rR) {
  88. 			printf("The last ant will fall down in %d seconds - strarted at %d and %d.\n", rL, min(retL,retR), max(retL,retR));
  89. 		}
  90. 		else {
  91. 			//printf("%d %d %d %d\n", rL, rR, retL, retR);
  92. 			int opt; int index;
  93. 			if (rL > rR) { opt = rL; index = retR; }
  94. 			else { opt = rR; index = retL; }
  95. 			printf("The last ant will fall down in %d seconds - strarted at %d.\n", opt, index);
  96. 		}
  97. 		return true;
  98. }
  99.  
  100. int main() {
  101. 		while(solve());
  102. 		return 0;
  103. }
  104.