Source code for submission s1038

ants.cpp

  1. #include <iomanip>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cstdio>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9. int number,length;
  10.  
  11. scanf("%d %d", &length, &number);
  12. int *start_pos = new int[number];
  13. int *act_pos = new int[number];
  14. int *dir = new int[number];
  15. for (int i=0; i < number; i++)
  16. start_pos[i]=0;
  17.  
  18. int *len=new int[number];
  19. int pos;
  20.  
  21. // read all inputs && count time for each ant
  22. for (int i=0; i < number; i++){
  23. char tmp;
  24. scanf("%d %c", &pos, &tmp);
  25. if (tmp == 'R' ){
  26. len[i]=length-pos;
  27. dir[i]=1;
  28.  
  29. }
  30. else {
  31. len[i]=pos;
  32. dir[i]=-1;
  33. }
  34. start_pos[i]=pos;
  35. act_pos[i]=pos;
  36. }
  37.  
  38. for (int i=0; i < number; i++){
  39. int max=start_pos[0];
  40. for (int j=0; j < number-1-i; j++){
  41. if (start_pos[i] > max){
  42. int tmp=start_pos[i];
  43. start_pos[i]=start_pos[i+1];
  44. start_pos[i+1]=tmp;
  45. tmp= act_pos[i];
  46. act_pos[i]=act_pos[i+1];
  47. act_pos[i+1]=tmp;
  48. tmp= dir[i];
  49. dir[i]=dir[i+1];
  50. dir[i+1]=tmp;
  51. }
  52.  
  53. }
  54. }
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61. // find max
  62. int max = len[0];
  63. for (int i=1; i < number; i++){
  64. if (len[i] > max){
  65. max = len[i];
  66. }
  67. }
  68.  
  69. //cout << "max found" << endl;
  70.  
  71. int *fin = new int [number];
  72. for (int i=0; i < number; i++)
  73. if (len[i] == -1);
  74.  
  75.  
  76. int nr=0;
  77. for (int i=0; i < number; i++){
  78. if (len[i] == max){
  79. fin[nr++]=i;
  80. }
  81. }
  82.  
  83.  
  84. int *used_pos = new int [length];
  85. for (int i=0; i < number; i++)
  86. used_pos[i]=0;
  87.  
  88. bool *alive = new bool [number];
  89. int aliveAnts=number;
  90. bool *preMoved = new bool [number];
  91.  
  92. int *id = new int [number];
  93.  
  94. // setup
  95. for (int i=0; i < number; i++){
  96. alive[i]=true;
  97. preMoved[i]=false;
  98. id[i]=i;
  99. }
  100.  
  101. for (int k=0; k < max-1; k++){
  102. //cout << "-------------" << endl;
  103. //cout << "time: " << k << endl;
  104.  
  105. // distance = 1, direction = crash ===> change direction, do NOT change actual position!
  106. for (int i=0; i < number-1; i++){
  107. if ((alive[i]==false)||(alive[i+1]==false))
  108. continue;
  109. if ((act_pos[i]+dir[i]==(act_pos[i+1])) && ((act_pos[i])==(act_pos[i+1]+dir[i+1]))){
  110. //cout << "crash 1 ants " << i << " and " << i+1 << " on pos " << act_pos[i] << "(+1)" << endl;
  111. preMoved[i]=true;
  112. dir[i]*=-1;
  113. preMoved[i+1]=true;
  114. dir[i+1]*=-1;
  115. }
  116. }
  117.  
  118.  
  119. // move
  120. for (int i=0; i < number; i++){
  121. if (preMoved[i]==true)
  122. continue;
  123. act_pos[i]+=dir[i];
  124. //cout << "ant " << i << " is on pos " << act_pos[i] << endl;
  125. }
  126.  
  127. // check for death ants
  128. for (int i=0; i < number; i++){
  129. if ((alive[i]==true)&&((act_pos[i]>=length)||(act_pos[i]<0))){
  130. alive[i]=false;
  131. aliveAnts--;
  132. //cout << "ant " << i << " died on pos " << act_pos[i] << endl;
  133. }
  134. }
  135.  
  136.  
  137. for (int i=0; i < length; i++){
  138. used_pos[i]=0;
  139. }
  140.  
  141. // distance = 2, direction = crash
  142. for (int i=0; i < number; i++){
  143. if (alive[i]==false)
  144. continue;
  145. used_pos[act_pos[i]]++;
  146. }
  147.  
  148. // if on 'same' pos => crash => change direction
  149. for (int i=0; i < length; i++){
  150. if (used_pos[i] > 1){
  151. for (int j=0; j < number; j++){
  152. if (act_pos[j]==i){
  153. dir[j]*=-1;
  154. //cout << "changing dir of ant " << j << " into " << dir[j] << endl;
  155. }
  156. }
  157. }
  158. }
  159.  
  160. }
  161.  
  162.  
  163. //cout << "before output" << endl;
  164.  
  165.  
  166.  
  167. cout << "The last ant will fall down in " << max << " seconds -" << " started at " << start_pos [fin[0]];
  168.  
  169. for (int i=1; i < nr; i++){
  170. cout << " and " << start_pos [fin[i]];
  171. }
  172.  
  173. cout << "."<<endl;
  174.  
  175. return 0;
  176. }
  177.  
  178.