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.