Source code for submission s1381

ants.cpp

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int L,A;
  7.  
  8. struct Mravenec {
  9. int Pos;
  10. int Cas;
  11. int Dir;
  12. int FallT;
  13. int SPos;
  14. };
  15.  
  16. int Kolize[100000];
  17. int KSize;
  18. int KLevy,KPravy;
  19. int KTime,KPos,KPos2;
  20.  
  21. bool ACmp(struct Mravenec M1,struct Mravenec M2) {
  22. return (M1.Pos < M2.Pos);
  23. };
  24.  
  25. vector<Mravenec> An;
  26.  
  27. int main() {
  28. int i;
  29. char c;
  30. int X;
  31. int Max;
  32. int MaxF;
  33. struct Mravenec Mr;
  34. struct Mravenec LMr,RMr;
  35.  
  36. while (scanf("%d%d",&L,&A)==2) {
  37. An.clear();
  38. for (i=0;i<A;i++) {
  39. scanf("%d",&X);
  40. scanf("%c",&c);
  41. while ((c!='R') && (c!='L')) scanf("%c",&c);
  42. Mr.Pos = X*2;
  43. Mr.Cas = 0;
  44. Mr.Dir = (c=='R')?+1:-1;
  45. Mr.SPos = X;
  46. An.push_back(Mr);
  47. };
  48. sort(An.begin(),An.end(),ACmp);
  49. //for (i=0;i<A;i++) printf("%d ",An[i].SPos);
  50. //printf("\n");
  51. KSize = 0;
  52. for (i=1;i<A;i++) {
  53. if ((An[i-1].Dir == +1) && (An[i].Dir == -1)) {
  54. Kolize[KSize++] = i-1;
  55. };
  56. };
  57. while (KSize > 0) {
  58. KLevy = Kolize[--KSize];
  59. KPravy = Kolize[KSize]+1;
  60. //printf("X %d %d",KLevy,KPravy);
  61. //printf("[%d %d %d %d] [%d %d %d %d]\n",An[KLevy].Pos,An[KLevy].Dir,An[KLevy].Cas,An[KLevy].SPos,An[KPravy].Pos,An[KPravy].Dir,An[KPravy].Cas,An[KPravy].SPos);
  62. LMr = An[KLevy];
  63. RMr = An[KPravy];
  64. KPos2 = RMr.Cas-LMr.Cas+LMr.Pos+RMr.Pos;
  65. KPos = KPos2/2;
  66. KTime = An[KLevy].Cas + KPos - An[KLevy].Pos;
  67. //printf("%d %d %d\n",KPos2,KPos,KTime);
  68. // i = An[KLevy].SPos;An[KLevy].SPos = An[KPravy].SPos;An[KPravy].SPos=i;
  69. An[KLevy].Dir = -1;An[KPravy].Dir = +1;
  70. An[KLevy].Cas = KTime;An[KPravy].Cas = KTime;
  71. An[KLevy].Pos = KPos;An[KPravy].Pos = KPos;
  72. //printf("[%d %d %d %d] [%d %d %d %d]\n",An[KLevy].Pos,An[KLevy].Dir,An[KLevy].Cas,An[KLevy].SPos,An[KPravy].Pos,An[KPravy].Dir,An[KPravy].Cas,An[KPravy].SPos);
  73. if (KLevy != 0) {
  74. if (An[KLevy-1].Dir == +1) {
  75. Kolize[KSize++]=KLevy-1;
  76. //printf("AddL %d\n",KLevy-1);
  77. };
  78. };
  79. if (KPravy < A-1) {
  80. if (An[KPravy+1].Dir == -1) {
  81. Kolize[KSize++]=KPravy;
  82. //printf("AddR %d\n",KPravy);
  83. };
  84. };
  85. };
  86. for (i=0;i<A;i++) if (An[i].Dir == -1) {
  87. An[i].FallT = An[i].Pos + An[i].Cas;
  88. } else {
  89. An[i].FallT = L*2 - An[i].Pos + An[i].Cas;
  90. };
  91. Max = -1;
  92. for (i=0;i<A;i++) if (An[i].FallT > Max) Max = An[i].FallT;
  93. printf("The last ant will fall down in %d seconds - started at ",Max/2);
  94. MaxF = 0;
  95. for (i=0;i<A;i++) {
  96. if (An[i].FallT == Max) {
  97. if (MaxF == 1) printf(" and ");
  98. printf("%d",An[i].SPos);
  99. MaxF = 1;
  100. };
  101. };
  102. printf(".\n");
  103. };
  104. return 0;
  105. };
  106.