Source code for submission s1392

Go to diff to previous submission

ants.cpp

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

Diff to submission s1343

ants.cpp

--- c4.s1343.cteam015.ants.cpp.0.ants.cpp
+++ c4.s1392.cteam015.ants.cpp.0.ants.cpp
@@ -143,5 +143,5 @@
 // check for death ants
 for  (int i=0; i < number; i++){
-        if ((alive[i]==true)&&((act_pos[i]>=length)||(act_pos[i]<0))){
+        if ((alive[i]==true)&&((act_pos[i]>length)||(act_pos[i]<0))){
                 alive[i]=false;
                 aliveAnts--;