Source code for submission s1321

ants.cpp

  1. #include<cstdlib>
  2. #include<cstdio>
  3. #include<cstring>
  4.  
  5. struct Ant{
  6. 		int pos;
  7. 		int srazky;
  8. 		bool dir; // true = left
  9. 		bool spadneDir;
  10. };
  11.  
  12. int compare(const void* a,const void* b){
  13. 	Ant* aa = (Ant*)a;
  14. 	Ant* bb = (Ant*)b;
  15. 	return aa->pos - bb->pos;
  16. }
  17.  
  18. #define antsSize 100005
  19.  
  20. int main()
  21. {
  22. 	Ant ants[antsSize];
  23. 	int antsNum,length;
  24. 	while(scanf("%d%d",&length,&antsNum)==2){
  25. 	int pos;char dir;
  26. 		for(int i=0; i<antsNum; i++){
  27. 			scanf("%d %c",&pos,&dir);
  28. 			ants[i].pos = pos;
  29. 			ants[i].dir = (dir == 'L');
  30. 		}
  31. 	qsort((void*)ants,antsNum,sizeof(Ant),compare);
  32. 	int timeL = 0,timeR = 0, timeMax;
  33. 	int i = 0;
  34. 	while(timeR==0 && i < antsNum){
  35. 		if(ants[i].dir == false)timeR = length - ants[i].pos;
  36. 		i++;
  37. 	}
  38. 	i = antsNum-1;
  39. 	while(timeL==0 && i>=0){
  40. 		if(ants[i].dir == true)timeL = ants[i].pos;
  41. 		i--;
  42. 	}
  43.  
  44. 	if(timeL > timeR) timeMax = timeL;
  45. 	else timeMax = timeR;
  46.  
  47. 	char vsichni = 0;
  48. 	// orezani tech, ktery se nesrazi a spadnou
  49. 	int orezLeft = 0; // index mravence, ktery jeste nespadne
  50. 	while(ants[orezLeft].dir == true){
  51. 		orezLeft++;
  52. 		if(orezLeft==antsNum){
  53. 			vsichni ='L';
  54. 			break; // všichni spadnou doleva
  55. 		}
  56. 	}
  57.  
  58. 	int orezRight = antsNum - 1; // index mravence, ktery jeste nespadne
  59. 	while(ants[orezRight].dir == false){
  60. 		orezRight--;
  61. 		if(orezRight==-1){
  62. 			vsichni ='R';
  63. 			break; // všichni spadnou doprava
  64. 		}
  65. 	}
  66.  
  67.  
  68.  
  69. 	for(int i=orezLeft; i<antsNum; i++){
  70. 		if(ants[i].dir == true){
  71. 			ants[i].srazky = 2*(i-orezLeft);
  72. 		} else{
  73. 			ants[i].srazky = 2*(i-orezLeft) + 1;
  74. 		}
  75. 		ants[i].spadneDir = true;
  76. 	}	
  77.  
  78. 	for(int i= orezRight/*(antsNum - 1)*/; i>=orezLeft; i--){
  79. 		if(ants[i].dir == true){
  80. 			if(ants[i].srazky > (2*(orezRight-i) + 1) ) {
  81. 				ants[i].srazky = 2*(orezRight-i) + 1;
  82. 				ants[i].spadneDir = false;
  83. 			}
  84. 			else{
  85. 				//break; // muzeme preskocit zbytek? tnz budou uz vsichni mit srazku nizsi
  86. 			}
  87. 		} else{
  88. 			if(ants[i].srazky > (2*(orezRight-i)) ) {			
  89. 				ants[i].srazky = 2*(orezRight-i);
  90. 				ants[i].spadneDir = false;
  91. 			}
  92. 			else{
  93. 				//break;
  94. 			}
  95. 		}
  96. 	}
  97. 	if(vsichni == 'R'){
  98. 		printf("The last ant will fall down in %d seconds - started at %d.\n", timeMax, ants[0].pos);
  99. 		continue;
  100. 	}
  101. 	if(vsichni == 'L'){
  102. 		printf("The last ant will fall down in %d seconds - started at %d.\n", timeMax, ants[antsNum-1].pos);
  103. 		continue;
  104. 	}
  105. 	//printf("times %d %d\n",timeL,timeR);
  106. 	int pos2=0xFF,pos3=-1;
  107. 	if(timeL==timeR){
  108. 		//printf("tu\n");
  109. 		for(i = antsNum-1;i>=0;i--){
  110. 				//printf("%d Spadne %d\n",i,ants[i].spadneDir);
  111. 				if(ants[i].spadneDir==true){
  112. 					pos2 = ants[i].pos;
  113. 					break;
  114. 				}
  115. 		}
  116. 		for(i = 0;i<antsNum;i++){
  117. 				if(ants[i].spadneDir==false){
  118. 					pos3 = ants[i].pos;
  119. 					break;
  120. 				}
  121. 		}
  122. 	}else{
  123. 		if(timeL==timeMax){
  124. 			for(i = antsNum-1;i>=0;i--){
  125. 				if(ants[i].spadneDir==true){
  126. 					pos2 = ants[i].pos;
  127. 					break;
  128. 				}
  129. 			}
  130. 		}else{
  131. 			for(i = 0;i<antsNum;i++){
  132. 				if(ants[i].spadneDir==false){
  133. 					pos2 = ants[i].pos;
  134. 					break;
  135. 				}
  136. 			}
  137. 		}
  138. 	}
  139. 	//printf("padne pos %d %d\n",pos2,pos3);
  140. 	if(pos3==-1){
  141. 	printf("The last ant will fall down in %d seconds - started at %d.\n", timeMax, pos2);
  142. 	}
  143. 	else{
  144. 		if(pos3<pos2){
  145. 			int pomoc = pos3;
  146. 			pos3 = pos2;
  147. 			pos2 = pomoc;
  148. 		}
  149. 		printf("The last ant will fall down in %d seconds - started at %d and %d.\n", timeMax, pos2,pos3);
  150. 	}
  151. 	//printf("Ořezy: %d %d\n",orezLeft, orezRight);
  152. 	for(int i = orezLeft; i<= orezRight; i++){
  153. 		//printf("%d ",ants[i].srazky);
  154. 	}
  155. 	}
  156. 	return 0;
  157. }
  158.  
  159. /*
  160.  
  161. for(int i=0;i<10;i++)
  162. {
  163.  
  164. 	 }
  165.  
  166. scanf("%d",&);
  167. printf("%d");
  168.  
  169.  
  170.  
  171. */
  172.