Source code for submission s1357

ants.cpp

  1. #include<iostream>
  2.  
  3. #include<vector>
  4. #include<algorithm>
  5. #include<map>
  6. #include<set>
  7. #include<list>
  8. #include<stack>
  9. #include<queue>
  10.  
  11. #include<stdio.h>
  12. #include<stdlib.h>
  13. #include<math.h>
  14. #include<string.h>
  15.  
  16. using namespace std;
  17.  
  18. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  19.  
  20. #define PB push_back
  21. #define PII pair<int,int>
  22. #define PLL pair<ll,ll>
  23. #define MP make_pair
  24. #define fi first
  25. #define se second
  26.  
  27. #define SIZE(s) (int) (s).size()
  28.  
  29. #define INF 987654321
  30. #define ll long long
  31.  
  32. //----------------------
  33.  
  34. int N;
  35. int dlzka;
  36.  
  37. vector< pair<int, char> > V;
  38. vector< pair<int, char> > V2;
  39.  
  40. int find(double val)
  41. {
  42. FOR(i,0,SIZE(V2)-1)
  43. if (V2[i].fi >= val) return i;
  44. return -1;
  45. }
  46.  
  47. void solve2(int lavy, int pravy,int kolko)
  48. {
  49. int pozL = V2[lavy].fi;
  50. int pozR = V2[pravy].fi;
  51. if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR);
  52. else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
  53. else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
  54. }
  55.  
  56. void solve1(int lavy, int pravy,int kolko)
  57. {
  58. if (lavy == -1)
  59. {
  60. int pozR = V[pravy].fi;
  61. printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
  62. }
  63. else if (pravy == -1)
  64. {
  65. int pozL = V[lavy].fi;
  66. printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
  67. }
  68. else
  69. {
  70. int pozL = V[lavy].fi;
  71. int pozR = V[pravy].fi;
  72. if (dlzka-pozR == pozL) printf("The last ant will fall down in %d seconds - started at %d and %d.\n",kolko,pozL,pozR);
  73. else if (dlzka-pozR > pozL) printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozR);
  74. else printf("The last ant will fall down in %d seconds - started at %d.\n",kolko,pozL);
  75. }
  76. }
  77.  
  78. int main()
  79. {
  80. char z;
  81. int poz;
  82.  
  83. while(scanf("%d %d",&dlzka,&N)==2)
  84. {
  85. V.clear();
  86. V2.clear();
  87.  
  88. int kolko=-1;
  89. int lavy = -1;
  90. int pravy = -1;
  91. bool existuje = false;
  92.  
  93. FOR(i,0,N-1)
  94. {
  95. scanf("%d %c",&poz,&z);
  96. //cout << poz << " " << z << endl;
  97. if (z == 'L') kolko = max(poz,kolko);
  98. else kolko = max(kolko,dlzka-poz);
  99. V.PB(MP(poz,z));
  100.  
  101. }
  102.  
  103. sort(V.begin(),V.end());
  104.  
  105. FOR(i,0,N-1)
  106. {
  107. if (i>0 && V[i-1].se == 'L' && V[i].se == 'R') existuje = true;
  108. if (V[i].se == 'L') lavy = i;
  109. if (pravy == -1 && V[i].se == 'R') pravy = i;
  110. }
  111.  
  112. // cout << lavy << endl;
  113. FOR(i,0,N-1)
  114. {
  115. if (pravy == -1 && V[i].se == 'L')
  116. {
  117.  
  118. }
  119. else
  120. V2.PB(V[i]);
  121. if (lavy > 0 && lavy == i) break;
  122. }
  123.  
  124. if (existuje)
  125. {
  126. int pozL = V2[0].fi;
  127. int pozR = V2[SIZE(V2)-1].fi;
  128. // cout << pozL << " " << pozR << endl;
  129. double stred = (pozL+pozR) / 2.0;
  130. int idx1 = find(stred);
  131. // cout << stred << " " << idx1 << endl;
  132.  
  133. int idx2 = idx1-1;
  134. solve2(idx2,idx1,kolko);
  135. }
  136. else
  137. {
  138. solve1(lavy,pravy,kolko);
  139. }
  140. }
  141.  
  142. return 0;
  143. }
  144.  
  145.