Source code for submission s1265

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

Diff to submission s1250

ants.cpp

--- c4.s1250.cteam015.ants.cpp.0.ants.cpp
+++ c4.s1265.cteam015.ants.cpp.0.ants.cpp
@@ -189,9 +184,10 @@
 //cout << "before output" << endl;
 
-
+if (nr > 2)
+        nr=2;
 
 cout << "The last ant will fall down in " << max << " seconds -" << " started at " << start_pos [fin[0]];
 
-for (int i=1; i < nr; i++){
+for (int i=1; i < dfas; i++){
 cout << " and " << start_pos [fin[i]];
 }