Source code for submission s1318

Go to diff to previous submission

ants.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <climits>
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9.  
  10. #include <vector>
  11. #include <string>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <stack>
  16. #include <set>
  17.  
  18. //~ using namespace std;
  19.  
  20. typedef long double num;
  21. typedef long long int lint;
  22. typedef struct { int x, y; } intpoint;
  23. typedef struct { num x, y; } numpoint;
  24. typedef struct { lint x, y; } lintpoint;
  25.  
  26. #define EPS (1e-7L)
  27. #define PI (4.0L * atanl(1.0L))
  28.  
  29. #define min(a, b) ((a) < (b) ? (a) : (b))
  30. #define max(a, b) ((a) > (b) ? (a) : (b))
  31. #define abs(a) ((a) < 0 ? -(a) : (a))
  32.  
  33. int main(int argc, char *argv[]) {
  34. 	while (true) {
  35. 		int ants, len;
  36.  
  37. 		if (2 != scanf("%u %u\n", &len, &ants))
  38. 			break;
  39.  
  40. 		int maxL = 0, minR = len, mindist = len;
  41. 		bool existL = false, existR = false;
  42. 		std::vector<int> antssssss;
  43. 		char wood[len + 1];
  44. 		memset(wood, 0, len + 1);
  45.  
  46. 		for (int ant = 0; ant < ants; ant++) {
  47. 			int start;
  48. 			char dir;
  49.  
  50. 			scanf("%u %c", &start, &dir);
  51.  
  52. 			if (dir == 'L') {
  53. 				existL = true;
  54. 				maxL = max(maxL, start);
  55. 			} else if (dir == 'R') {
  56. 				existR = true;
  57. 				minR = min(minR, start);
  58. 			}
  59. 			wood[start] = dir;
  60.  
  61. 			int aux = len%2 ? min(abs(len/2 - start), abs(len/2 + 1 - start)) : abs((len >>1) - start);
  62.  
  63. 			if (aux < mindist) 
  64. 			{
  65. 				antssssss.clear();
  66. 				antssssss.push_back(start);
  67. 				mindist = aux;
  68. 			}
  69. 			else
  70. 				if(aux == mindist)
  71. 					antssssss.push_back(start);
  72. 		}
  73.  
  74. 		bool debug = true;
  75. 		if (debug) { for (int i = 0; i <= len; i++) putchar(wood[i] == '\0' ? '0' : wood[i]); putchar('\n'); }
  76.  
  77. 		int L = maxL, R = len - minR;
  78. 		if (existL && existR) {
  79. 			if (minR < maxL) {
  80. 				int cl = len / 2, cr = len / 2 + (len % 2);
  81. 				if (debug) printf("cl: %d cr: %d\n", cl, cr);
  82.  
  83. 				int dl = INT_MAX, dr = INT_MAX;
  84. 				bool hasl, hasr;
  85. 				bool hasR, hasL;
  86.  
  87. 				bool haslL = false, haslR = false;
  88. 				int lL, lR, dlL, dlR;
  89. 				for (int l = cl; l >= 0; l--) {
  90. 					if (haslL && haslR)
  91. 						break;
  92.  
  93. 					if (!haslL && wood[l] == 'L') {
  94. 						haslL = hasL = hasl = true;
  95. 						lL = l;
  96. 						dlL = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
  97. 						if (dlL < dl)
  98. 							dl = dlL;
  99. 					} else if (!haslR && wood[l] == 'R') {
  100. 						haslR = hasR = hasl = true;
  101. 						lR = l;
  102. 						dlR = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
  103. 						if (dlR < dl)
  104. 							dl = dlR;
  105. 					}
  106. 				}
  107. 				if (debug) printf("haslL: %d lL: %d dlL: %d\n", haslL, lL, dlL);
  108. 				if (debug) printf("haslR: %d lR: %d dlR: %d\n", haslR, lR, dlR);
  109.  
  110. 				bool hasrL = false, hasrR = false;
  111. 				int rL, rR, drL, drR;
  112. 				for (int r = cr; r <= len; r++) {
  113. 					if (hasrL && hasrR)
  114. 						break;
  115.  
  116. 					if (!hasrL && wood[r] == 'L') {
  117. 						hasrL = hasL = hasr = true;
  118. 						rL = r;
  119. 						drL = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
  120. 						if (drL < dr)
  121. 							dr = drL;
  122. 					} else if (!hasrR && wood[r] == 'R') {
  123. 						hasrR = hasR = hasr = true;
  124. 						rR = r;
  125. 						drR = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
  126. 						if (drR < dr)
  127. 							dr = drR;
  128. 					}
  129. 				}
  130. 				if (debug) printf("hasrL: %d rL: %d drL: %d\n", hasrL, rL, drL);
  131. 				if (debug) printf("hasrR: %d rR: %d drR: %d\n", hasrR, rR, drR);
  132.  
  133. 				int result1, result2;
  134.  
  135. 				if (hasl && hasr) {
  136. 					if (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR)) {
  137. 						if (dlR == drR) {
  138. 							result1 = lR;
  139. 							result2 = rL;
  140. 						} else if (dlR < drL) {
  141. 							result1 = lR;
  142. 							result2 = -1;
  143. 						} else if (drL < dlR) {
  144. 							result1 = rL;
  145. 							result2 = -1;
  146. 						}
  147. 					} else if (haslL && hasrR && (!haslR || lR < lL) && (!hasrL || rR < rL)) {
  148. 						if (dlL == drR && haslR && lR < lL && hasrL && rR < rL) {
  149. 							result1 = lL;
  150. 							result2 = rR;
  151. 						} else if (dlL < drR && haslR && lR < lL) {
  152. 							result1 = lL;
  153. 							result2 = -1;
  154. 						} else if (drR < dlL && hasrL && rR < rL) {
  155. 							result1 = rR;
  156. 							result2 = -1;
  157. 						}
  158. 					}
  159. 				} else if (hasl) { // mame haslR, haslL // lR < lL
  160. 					result1 = lL;
  161. 					result2 = -1;
  162. 				} else if (hasr) { // mame hasrR, hasrL // rR < rL
  163. 					result1 = rR;
  164. 					result2 = -1;
  165. 				} else {
  166. 					printf("not gonna happen, ever!!!\n");
  167. 				}
  168. 				/* 
  169. 				if (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR)) {
  170. 					result1 = lR;
  171. 					result2 = rL;
  172. 					if (debug) printf("%d: (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR))\n", __LINE__);
  173. 				} else if (haslR && haslL && (lR < lL) && hasrR && hasrL && (rR < rL)) {
  174. 					//~ if (dlL < drR) {
  175. 						//~ result1 = lR;
  176. 						//~ result2 = lL;
  177. 					//~ } else if (dlL > drR) {
  178. 						//~ result1 = rL;
  179. 						//~ result2 = rR;
  180. 					//~ } else {
  181. 						result1 = lL;
  182. 						result2 = rR;
  183. 					//~ }
  184. 					if (debug) printf("%d: ((haslR && haslL && (lR < lL) && hasrR && hasrL && (rL < rR))\n", __LINE__);
  185. 				} else if (haslR && haslL && (lR < lL)) {
  186. 					result1 = lR; 
  187. 					result2 = lL;
  188. 					if (debug) printf("%d: (haslR && haslL && (lR < lL))\n", __LINE__);
  189. 				} else if (hasrR && hasrL && (rR < rL)) {
  190. 					result1 = rR;
  191. 					result2 = rL;
  192. 					if (debug) printf("%d: (hasrR && hasrL && (rL < rR))\n", __LINE__);
  193. 				} else if (haslR && haslL && (lR > lL)) {
  194. 					result1 = lL; 
  195. 					result2 = -1;
  196. 					if (debug) printf("%d: (haslR && haslL && (lR < lL))\n", __LINE__);
  197. 				} else if (hasrR && hasrL && (rR > rL)) {
  198. 					result1 = rR;
  199. 					result2 = -1;
  200. 					if (debug) printf("%d: (hasrR && hasrL && (rL < rR))\n", __LINE__);
  201. 				} else {
  202. 					// not gonna happen
  203. 					printf("Bleee\n\n");
  204. 				} */
  205.  
  206. 				if (result2 == -1)
  207. 					printf("The last ant will fall down in %d seconds - started at %d.\n", max(L, R), result1);
  208. 				else
  209. 					printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max(L, R), min(result1, result2), max(result1, result2));
  210. 			} else {
  211. 				if(antssssss.size() == 2)
  212. 					printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max(L, R), antssssss[0], antssssss[1]);
  213. 				else
  214. 					printf("The last ant will fall down in %d seconds - started at %d.\n", max(L, R), antssssss[0]);
  215. 			}
  216. 		} else if (existR) {
  217. 			printf("The last ant will fall down in %d seconds - started at %d.\n", R, minR);
  218. 		} else if (existL) {
  219. 			printf("The last ant will fall down in %d seconds - started at %d.\n", L, maxL);
  220. 		} else {
  221. 			// not gonna happen
  222. 		}
  223. 	}
  224.  
  225. 	return 0;
  226. }
  227.  

Diff to submission s1199

ants.cpp

--- c4.s1199.cteam101.ants.cpp.0.ants.cpp
+++ c4.s1318.cteam101.ants.cpp.0.ants.cpp
@@ -72,5 +72,5 @@
                 }
                 
-                bool debug = false;
+                bool debug = true;
                 if (debug) { for (int i = 0; i <= len; i++) putchar(wood[i] == '\0' ? '0' : wood[i]); putchar('\n'); }
                 
@@ -81,4 +81,8 @@
                                 if (debug) printf("cl: %d cr: %d\n", cl, cr);
                                 
+                                int dl = INT_MAX, dr = INT_MAX;
+                                bool hasl, hasr;
+                                bool hasR, hasL;
+                                
                                 bool haslL = false, haslR = false;
                                 int lL, lR, dlL, dlR;
@@ -88,11 +92,15 @@
                                         
                                         if (!haslL && wood[l] == 'L') {
-                                                haslL = true;
+                                                haslL = hasL = hasl = true;
                                                 lL = l;
                                                 dlL = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
+                                                if (dlL < dl)
+                                                        dl = dlL;
                                         } else if (!haslR && wood[l] == 'R') {
-                                                haslR = true;
+                                                haslR = hasR = hasl = true;
                                                 lR = l;
                                                 dlR = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
+                                                if (dlR < dl)
+                                                        dl = dlR;
                                         }
                                 }
@@ -107,11 +115,15 @@
                                         
                                         if (!hasrL && wood[r] == 'L') {
-                                                hasrL = true;
+                                                hasrL = hasL = hasr = true;
                                                 rL = r;
                                                 drL = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
+                                                if (drL < dr)
+                                                        dr = drL;
                                         } else if (!hasrR && wood[r] == 'R') {
-                                                hasrR = true;
+                                                hasrR = hasR = hasr = true;
                                                 rR = r;
                                                 drR = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
+                                                if (drR < dr)
+                                                        dr = drR;
                                         }
                                 }
@@ -121,4 +133,38 @@
                                 int result1, result2;
                                 
+                                if (hasl && hasr) {
+                                        if (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR)) {
+                                                if (dlR == drR) {
+                                                        result1 = lR;
+                                                        result2 = rL;
+                                                } else if (dlR < drL) {
+                                                        result1 = lR;
+                                                        result2 = -1;
+                                                } else if (drL < dlR) {
+                                                        result1 = rL;
+                                                        result2 = -1;
+                                                }
+                                        } else if (haslL && hasrR && (!haslR || lR < lL) && (!hasrL || rR < rL)) {
+                                                if (dlL == drR && haslR && lR < lL && hasrL && rR < rL) {
+                                                        result1 = lL;
+                                                        result2 = rR;
+                                                } else if (dlL < drR && haslR && lR < lL) {
+                                                        result1 = lL;
+                                                        result2 = -1;
+                                                } else if (drR < dlL && hasrL && rR < rL) {
+                                                        result1 = rR;
+                                                        result2 = -1;
+                                                }
+                                        }
+                                } else if (hasl) { // mame haslR, haslL // lR < lL
+                                        result1 = lL;
+                                        result2 = -1;
+                                } else if (hasr) { // mame hasrR, hasrL // rR < rL
+                                        result1 = rR;
+                                        result2 = -1;
+                                } else {
+                                        printf("not gonna happen, ever!!!\n");
+                                }
+                                /* 
                                 if (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR)) {
                                         result1 = lR;
@@ -156,5 +202,5 @@
                                         // not gonna happen
                                         printf("Bleee\n\n");
-                                }
+                                } */
                                 
                                 if (result2 == -1)