Source code for submission s1199

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 = false;
  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. 				bool haslL = false, haslR = false;
  84. 				int lL, lR, dlL, dlR;
  85. 				for (int l = cl; l >= 0; l--) {
  86. 					if (haslL && haslR)
  87. 						break;
  88.  
  89. 					if (!haslL && wood[l] == 'L') {
  90. 						haslL = true;
  91. 						lL = l;
  92. 						dlL = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
  93. 					} else if (!haslR && wood[l] == 'R') {
  94. 						haslR = true;
  95. 						lR = l;
  96. 						dlR = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
  97. 					}
  98. 				}
  99. 				if (debug) printf("haslL: %d lL: %d dlL: %d\n", haslL, lL, dlL);
  100. 				if (debug) printf("haslR: %d lR: %d dlR: %d\n", haslR, lR, dlR);
  101.  
  102. 				bool hasrL = false, hasrR = false;
  103. 				int rL, rR, drL, drR;
  104. 				for (int r = cr; r <= len; r++) {
  105. 					if (hasrL && hasrR)
  106. 						break;
  107.  
  108. 					if (!hasrL && wood[r] == 'L') {
  109. 						hasrL = true;
  110. 						rL = r;
  111. 						drL = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
  112. 					} else if (!hasrR && wood[r] == 'R') {
  113. 						hasrR = true;
  114. 						rR = r;
  115. 						drR = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
  116. 					}
  117. 				}
  118. 				if (debug) printf("hasrL: %d rL: %d drL: %d\n", hasrL, rL, drL);
  119. 				if (debug) printf("hasrR: %d rR: %d drR: %d\n", hasrR, rR, drR);
  120.  
  121. 				int result1, result2;
  122.  
  123. 				if (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR)) {
  124. 					result1 = lR;
  125. 					result2 = rL;
  126. 					if (debug) printf("%d: (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR))\n", __LINE__);
  127. 				} else if (haslR && haslL && (lR < lL) && hasrR && hasrL && (rR < rL)) {
  128. 					//~ if (dlL < drR) {
  129. 						//~ result1 = lR;
  130. 						//~ result2 = lL;
  131. 					//~ } else if (dlL > drR) {
  132. 						//~ result1 = rL;
  133. 						//~ result2 = rR;
  134. 					//~ } else {
  135. 						result1 = lL;
  136. 						result2 = rR;
  137. 					//~ }
  138. 					if (debug) printf("%d: ((haslR && haslL && (lR < lL) && hasrR && hasrL && (rL < rR))\n", __LINE__);
  139. 				} else if (haslR && haslL && (lR < lL)) {
  140. 					result1 = lR; 
  141. 					result2 = lL;
  142. 					if (debug) printf("%d: (haslR && haslL && (lR < lL))\n", __LINE__);
  143. 				} else if (hasrR && hasrL && (rR < rL)) {
  144. 					result1 = rR;
  145. 					result2 = rL;
  146. 					if (debug) printf("%d: (hasrR && hasrL && (rL < rR))\n", __LINE__);
  147. 				} else if (haslR && haslL && (lR > lL)) {
  148. 					result1 = lL; 
  149. 					result2 = -1;
  150. 					if (debug) printf("%d: (haslR && haslL && (lR < lL))\n", __LINE__);
  151. 				} else if (hasrR && hasrL && (rR > rL)) {
  152. 					result1 = rR;
  153. 					result2 = -1;
  154. 					if (debug) printf("%d: (hasrR && hasrL && (rL < rR))\n", __LINE__);
  155. 				} else {
  156. 					// not gonna happen
  157. 					printf("Bleee\n\n");
  158. 				}
  159.  
  160. 				if (result2 == -1)
  161. 					printf("The last ant will fall down in %d seconds - started at %d.\n", max(L, R), result1);
  162. 				else
  163. 					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));
  164. 			} else {
  165. 				if(antssssss.size() == 2)
  166. 					printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max(L, R), antssssss[0], antssssss[1]);
  167. 				else
  168. 					printf("The last ant will fall down in %d seconds - started at %d.\n", max(L, R), antssssss[0]);
  169. 			}
  170. 		} else if (existR) {
  171. 			printf("The last ant will fall down in %d seconds - started at %d.\n", R, minR);
  172. 		} else if (existL) {
  173. 			printf("The last ant will fall down in %d seconds - started at %d.\n", L, maxL);
  174. 		} else {
  175. 			// not gonna happen
  176. 		}
  177. 	}
  178.  
  179. 	return 0;
  180. }
  181.  

Diff to submission s922

ants.cpp

--- c4.s922.cteam101.ants.cpp.0.ants.cpp
+++ c4.s1199.cteam101.ants.cpp.0.ants.cpp
@@ -35,12 +35,12 @@
                 int ants, len;
                 
-                bool existL = false, existR = false, collision;
-                
                 if (2 != scanf("%u %u\n", &len, &ants))
                         break;
+                
                 int maxL = 0, minR = len, mindist = len;
+                bool existL = false, existR = false;
                 std::vector<int> antssssss;
-                
-                
+                char wood[len + 1];
+                memset(wood, 0, len + 1);
                 
                 for (int ant = 0; ant < ants; ant++) {
@@ -48,5 +48,5 @@
                         char dir;
                         
-                        scanf("%u %c\n", &start, &dir);
+                        scanf("%u %c", &start, &dir);
                         
                         if (dir == 'L') {
@@ -57,21 +57,110 @@
                                 minR = min(minR, start);
                         }
+                        wood[start] = dir;
+                        
                         int aux = len%2 ? min(abs(len/2 - start), abs(len/2 + 1 - start)) : abs((len >>1) - start);
-                                if (aux < mindist) 
-                                {
-                                        antssssss.clear();
+                        
+                        if (aux < mindist) 
+                        {
+                                antssssss.clear();
+                                antssssss.push_back(start);
+                                mindist = aux;
+                        }
+                        else
+                                if(aux == mindist)
                                         antssssss.push_back(start);
-                                        mindist = aux;
-                                }
-                                else
-                                        if(aux == mindist)
-                                                antssssss.push_back(start);
                 }
                 
-
+                bool debug = false;
+                if (debug) { for (int i = 0; i <= len; i++) putchar(wood[i] == '\0' ? '0' : wood[i]); putchar('\n'); }
                 
                 int L = maxL, R = len - minR;
                 if (existL && existR) {
                         if (minR < maxL) {
+                                int cl = len / 2, cr = len / 2 + (len % 2);
+                                if (debug) printf("cl: %d cr: %d\n", cl, cr);
+                                
+                                bool haslL = false, haslR = false;
+                                int lL, lR, dlL, dlR;
+                                for (int l = cl; l >= 0; l--) {
+                                        if (haslL && haslR)
+                                                break;
+                                        
+                                        if (!haslL && wood[l] == 'L') {
+                                                haslL = true;
+                                                lL = l;
+                                                dlL = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
+                                        } else if (!haslR && wood[l] == 'R') {
+                                                haslR = true;
+                                                lR = l;
+                                                dlR = len%2 ? min(abs(len/2 - l), abs(len/2 + 1 - l)) : abs((len >>1) - l);
+                                        }
+                                }
+                                if (debug) printf("haslL: %d lL: %d dlL: %d\n", haslL, lL, dlL);
+                                if (debug) printf("haslR: %d lR: %d dlR: %d\n", haslR, lR, dlR);
+                                
+                                bool hasrL = false, hasrR = false;
+                                int rL, rR, drL, drR;
+                                for (int r = cr; r <= len; r++) {
+                                        if (hasrL && hasrR)
+                                                break;
+                                        
+                                        if (!hasrL && wood[r] == 'L') {
+                                                hasrL = true;
+                                                rL = r;
+                                                drL = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
+                                        } else if (!hasrR && wood[r] == 'R') {
+                                                hasrR = true;
+                                                rR = r;
+                                                drR = len%2 ? min(abs(len/2 - r), abs(len/2 + 1 - r)) : abs((len >>1) - r);
+                                        }
+                                }
+                                if (debug) printf("hasrL: %d rL: %d drL: %d\n", hasrL, rL, drL);
+                                if (debug) printf("hasrR: %d rR: %d drR: %d\n", hasrR, rR, drR);
+                                
+                                int result1, result2;
+                                
+                                if (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR)) {
+                                        result1 = lR;
+                                        result2 = rL;
+                                        if (debug) printf("%d: (haslR && hasrL && (!haslL || lL < lR) && (!hasrR || rL < rR))\n", __LINE__);
+                                } else if (haslR && haslL && (lR < lL) && hasrR && hasrL && (rR < rL)) {
+                                        //~ if (dlL < drR) {
+                                                //~ result1 = lR;
+                                                //~ result2 = lL;
+                                        //~ } else if (dlL > drR) {
+                                                //~ result1 = rL;
+                                                //~ result2 = rR;
+                                        //~ } else {
+                                                result1 = lL;
+                                                result2 = rR;
+                                        //~ }
+                                        if (debug) printf("%d: ((haslR && haslL && (lR < lL) && hasrR && hasrL && (rL < rR))\n", __LINE__);
+                                } else if (haslR && haslL && (lR < lL)) {
+                                        result1 = lR; 
+                                        result2 = lL;
+                                        if (debug) printf("%d: (haslR && haslL && (lR < lL))\n", __LINE__);
+                                } else if (hasrR && hasrL && (rR < rL)) {
+                                        result1 = rR;
+                                        result2 = rL;
+                                        if (debug) printf("%d: (hasrR && hasrL && (rL < rR))\n", __LINE__);
+                                } else if (haslR && haslL && (lR > lL)) {
+                                        result1 = lL; 
+                                        result2 = -1;
+                                        if (debug) printf("%d: (haslR && haslL && (lR < lL))\n", __LINE__);
+                                } else if (hasrR && hasrL && (rR > rL)) {
+                                        result1 = rR;
+                                        result2 = -1;
+                                        if (debug) printf("%d: (hasrR && hasrL && (rL < rR))\n", __LINE__);
+                                } else {
+                                        // not gonna happen
+                                        printf("Bleee\n\n");
+                                }
+                                
+                                if (result2 == -1)
+                                        printf("The last ant will fall down in %d seconds - started at %d.\n", max(L, R), result1);
+                                else
+                                        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));
+                        } else {
                                 if(antssssss.size() == 2)
                                         printf("The last ant will fall down in %d seconds - started at %d and %d.\n", max(L, R), antssssss[0], antssssss[1]);