Source code for submission s983

Go to diff to previous submission

sablona.cc

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <sstream>
  12.  
  13. #include <stdio.h>
  14. #include <ctype.h>
  15. #include <math.h>
  16. #include <string.h>
  17. #include <stdlib.h>
  18.  
  19. using namespace std;
  20.  
  21. #define X first
  22. #define Y second
  23. #define MP make_pair
  24. #define PB push_back
  25. #define SZ size
  26. #define LEFT(i) 2*(i)
  27. #define RIGHT(i) 2*(i)+1
  28. #define PARENT(i) (i)/2
  29.  
  30. struct HeapVrchol
  31. {
  32. pair<int, int> vrchol;
  33. int value;
  34. };
  35.  
  36. struct HeapVrchol heap[10000];
  37. int heapSize = 0;
  38.  
  39. void vymenCisla(int *a, int *b)
  40. {
  41. int tmp = *a;
  42.  
  43. *a = *b;
  44. *b = tmp;
  45. }
  46.  
  47. void heapify(struct HeapVrchol *heap, int i, int heapSize)
  48. {
  49. int najvacsi;
  50. pair<int, int> tmp;
  51.  
  52. int l = LEFT(i);
  53. int r = RIGHT(i);
  54.  
  55. najvacsi = (((l <= heapSize) && (heap[l].value < heap[i].value)) ? l : i);
  56.  
  57. if((r <= heapSize) && (heap[r].value < heap[najvacsi].value))
  58. najvacsi = r;
  59.  
  60. if(najvacsi != i)
  61. {
  62. vymenCisla(&(heap[i].value), &(heap[najvacsi].value));
  63. tmp = heap[i].vrchol;
  64. heap[i].vrchol = heap[najvacsi].vrchol;
  65. heap[najvacsi].vrchol = tmp;
  66.  
  67. heapify(heap, najvacsi, heapSize);
  68. }
  69. }
  70.  
  71.  
  72. void heapInsert(pair<int, int> vrchol, int dlzka)
  73. {
  74. heapSize++;
  75. int i = heapSize;
  76.  
  77. if(heapSize == 1)
  78. {
  79. heap[i].vrchol = vrchol;
  80. heap[i].value = dlzka;
  81.  
  82. return ;
  83.  
  84. }
  85.  
  86. while(i > 1 && heap[PARENT(i)].value > dlzka)
  87. {
  88. heap[i].value = heap[PARENT(i)].value;
  89. heap[i].vrchol = heap[PARENT(i)].vrchol;
  90. i = PARENT(i);
  91. }
  92.  
  93.  
  94. heap[i].vrchol = vrchol;
  95. heap[i].value = dlzka;
  96. }
  97.  
  98. pair<int, int> heapNajmensiVrchol()
  99. {
  100. pair<int, int> min;
  101. //printf("%d\n", heapSize);
  102. if (heapSize > 0) {
  103. min = heap[1].vrchol;
  104. heap[1] = heap[heapSize];
  105.  
  106. heapSize--;
  107.  
  108. heapify(heap, 1, heapSize);
  109.  
  110. return min;
  111. }
  112. min = MP(-1, -1);
  113. return min;
  114.  
  115. }
  116.  
  117. int main(void)
  118. {
  119. int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k;
  120. int vrcholy[110][110];
  121. int uz[110][110];
  122. pair <int, int> pom;
  123. while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
  124. heapSize = 0;
  125. for (i = 1; i <= a; i++) {
  126. for (ii = 1; ii <= b; ii++) {
  127. vrcholy[i][ii] = 9999999;
  128. uz[i][ii] = -1;
  129. }
  130. }
  131. vrcholy[c][d] = 0;
  132. uz[c][d] = 1;
  133. akt = c;
  134. akt2 = d;
  135. if (akt - 1 > 0 && akt2 - 2 > 0)
  136. if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) {
  137. vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  138. heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1);
  139. }
  140. if (akt - 2 > 0 && akt2 - 1 > 0)
  141. if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) {
  142. vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  143. heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1);
  144. }
  145. if (akt + 1 <= a && akt2 - 2 > 0)
  146. if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) {
  147. vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  148. heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1);
  149. }
  150. if (akt + 2 <= a && akt2 - 1 > 0)
  151. if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) {
  152. vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  153. heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1);
  154. }
  155. if (akt - 1 > 0 && akt2 +2 <= b)
  156. if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) {
  157. vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  158. heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1);
  159. }
  160. if (akt - 2 > 0 && akt2 +1 <= b)
  161. if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) {
  162. vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1;
  163. heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1);
  164. }
  165. if (akt + 1 <= a && akt2 + 2 <= b)
  166. if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) {
  167. vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  168. heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1);
  169. }
  170. if (akt + 2 <= a && akt2 + 1 <= b)
  171. if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) {
  172. vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1;
  173. heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1);
  174. }
  175. int ok = 1;
  176. while (ok == 1) {
  177. akt = -1;
  178. akt2 = -1;
  179. /*for (j = 1; j <= a; j++) {
  180.   for (k = 1; k <= b; k++) {
  181.   if (uz[j][k] == -1 && (akt == -1 || vrcholy[j][k] < vrcholy[akt][akt2]) && vrcholy[j][k] != 9999999) {
  182.   akt = j;
  183.   akt2 = k;
  184.   }
  185.   }
  186.   }*/
  187. pom = heapNajmensiVrchol();
  188. akt = pom.first;
  189. akt2 = pom.second;
  190. //printf("%d %d\n", akt, akt2);
  191. if (akt != -1) {
  192. uz[akt][akt2] = 1;
  193. /*if (akt == 5 && akt2 == 3)
  194.   printf("uch %d %d %d\n", uz[3][2], vrcholy[3][2], heapSize);*/
  195. if (akt - 1 > 0 && akt2 - 2 > 0)
  196. if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) {
  197. vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  198. heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1);
  199. }
  200. if (akt - 2 > 0 && akt2 - 1 > 0)
  201. if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) {
  202. vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  203. heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1);
  204. }
  205. if (akt + 1 <= a && akt2 - 2 > 0)
  206. if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) {
  207. vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
  208. heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1);
  209. }
  210. if (akt + 2 <= a && akt2 - 1 > 0)
  211. if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) {
  212. vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
  213. heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1);
  214. }
  215. if (akt - 1 > 0 && akt2 +2 <= b)
  216. if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) {
  217. vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  218. heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1);
  219. }
  220. if (akt - 2 > 0 && akt2 +1 <= b)
  221. if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) {
  222. vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1;
  223. heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1);
  224. }
  225. if (akt + 1 <= a && akt2 + 2 <= b)
  226. if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) {
  227. vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
  228. heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1);
  229. }
  230. if (akt + 2 <= a && akt2 + 1 <= b)
  231. if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) {
  232. vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1;
  233. heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1);
  234. }
  235. } else {
  236. ok = 0;
  237. }
  238. }
  239. if (vrcholy[e][f] != 9999999)
  240. printf("%d\n", vrcholy[e][f]);
  241. else
  242. printf("impossible\n");
  243. }
  244.  
  245.  
  246. return 0;
  247. }
  248.  

Diff to submission s761

hop.cc

--- c4.s761.cteam079.grasshop.cpp.0.hop.cc
+++ c4.s983.cteam079.grasshop.cpp.0.sablona.cc
@@ -24,64 +24,224 @@
 #define PB push_back
 #define SZ size
+#define LEFT(i) 2*(i)
+#define RIGHT(i) 2*(i)+1
+#define PARENT(i) (i)/2
 
-int over(int akt, int akt2, int a, int b) {
-            if (akt - 1 > 0 && akt2 - 2 > 0)
-               return 1;
+struct HeapVrchol
+{
+   pair<int, int> vrchol;
+   int value;
+};
+
+struct HeapVrchol heap[10000];
+int heapSize = 0;
+
+void vymenCisla(int *a, int *b)
+{
+   int tmp = *a;
+   
+   *a = *b;
+   *b = tmp;
+}
+
+void heapify(struct HeapVrchol *heap, int i, int heapSize)
+{
+   int najvacsi;
+   pair<int, int> tmp;
+   
+   int l = LEFT(i);
+   int r = RIGHT(i);
+   
+   najvacsi = (((l <= heapSize) && (heap[l].value < heap[i].value)) ? l : i);
+   
+   if((r <= heapSize) && (heap[r].value < heap[najvacsi].value))
+      najvacsi = r;
+      
+   if(najvacsi != i)
+   {
+      vymenCisla(&(heap[i].value), &(heap[najvacsi].value));
+      tmp = heap[i].vrchol;
+      heap[i].vrchol = heap[najvacsi].vrchol;
+      heap[najvacsi].vrchol = tmp;
+      
+      heapify(heap, najvacsi, heapSize);
+   }
+}
+
+
+void heapInsert(pair<int, int> vrchol, int dlzka)
+{
+   heapSize++;
+   int i = heapSize;
+   
+   if(heapSize == 1)
+   {
+      heap[i].vrchol = vrchol;
+      heap[i].value = dlzka;
+      
+      return ;
+   
+   }
+
+   while(i > 1 && heap[PARENT(i)].value > dlzka)
+   {
+      heap[i].value = heap[PARENT(i)].value;
+      heap[i].vrchol = heap[PARENT(i)].vrchol;
+      i = PARENT(i);
+   }
+   
+   
+   heap[i].vrchol = vrchol;
+   heap[i].value = dlzka;
+}
+
+pair<int, int> heapNajmensiVrchol()
+{
+   pair<int, int> min;
+   //printf("%d\n", heapSize);
+   if (heapSize > 0) {
+      min = heap[1].vrchol;
+      heap[1] = heap[heapSize];
+      
+      heapSize--;
+      
+      heapify(heap, 1, heapSize);
+      
+      return min;
+   }
+   min = MP(-1, -1);
+   return min;
+   
+}
+
+int main(void)
+{
+   int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k;
+   int vrcholy[110][110];
+   int uz[110][110];
+   pair <int, int> pom;
+   while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
+      heapSize = 0;
+      for (i = 1; i <= a; i++) {
+         for (ii = 1; ii <= b; ii++) {
+            vrcholy[i][ii] = 9999999;
+            uz[i][ii] = -1;
+         }
+      }
+      vrcholy[c][d] = 0;
+      uz[c][d] = 1;
+      akt = c;
+      akt2 = d;
+      if (akt - 1 > 0 && akt2 - 2 > 0)
+               if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) {
+                  vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1);
+               }
             if (akt - 2 > 0 && akt2 - 1 > 0)
-               return 1;
+               if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) {
+                  vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1);
+               }
             if (akt + 1 <= a && akt2 - 2 > 0)
-               return 1;
+               if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) {
+                  vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1);
+               }
             if (akt + 2 <= a && akt2 - 1 > 0)
-               return 1;
+               if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) {
+                  vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1);
+               }
             if (akt - 1 > 0 && akt2 +2 <= b)
-               return 1;
+               if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) {
+                  vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1);
+               }
             if (akt - 2 > 0 && akt2 +1 <= b)
-               return 1;
+               if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) {
+                  vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1);
+               }
             if (akt + 1 <= a && akt2 + 2 <= b)
-               return 1;
+               if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) {
+                  vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1);
+               }
+            if (akt + 2 <= a && akt2 + 1 <= b)
+               if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) {
+                  vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1);
+               }
+               int ok = 1;
+      while (ok == 1) {
+            akt = -1;
+            akt2 = -1;
+            /*for (j = 1; j <= a; j++) {
+               for (k = 1; k <= b; k++) {
+                  if (uz[j][k] == -1 && (akt == -1 || vrcholy[j][k] < vrcholy[akt][akt2]) && vrcholy[j][k] != 9999999) {
+                     akt = j;
+                     akt2 = k;
+                  }
+               }
+            }*/
+            pom = heapNajmensiVrchol();
+            akt = pom.first;
+            akt2 = pom.second;
+            //printf("%d %d\n", akt, akt2);
+            if (akt != -1) {
+            uz[akt][akt2] = 1;
+            /*if (akt == 5 && akt2 == 3)
+               printf("uch %d %d %d\n", uz[3][2], vrcholy[3][2], heapSize);*/
+            if (akt - 1 > 0 && akt2 - 2 > 0)
+               if (vrcholy[akt - 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 - 2] == -1) {
+                  vrcholy[akt - 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-1, akt2 - 2), vrcholy[akt][akt2] + 1);
+               }
+            if (akt - 2 > 0 && akt2 - 1 > 0)
+               if (vrcholy[akt - 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 - 1] == -1) {
+                  vrcholy[akt - 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-2, akt2 - 1), vrcholy[akt][akt2] + 1);
+               }
+            if (akt + 1 <= a && akt2 - 2 > 0)
+               if (vrcholy[akt + 1][akt2 - 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 - 2] == -1) {
+                  vrcholy[akt + 1][akt2 - 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+1, akt2-2), vrcholy[akt][akt2] + 1);
+               }
+            if (akt + 2 <= a && akt2 - 1 > 0)
+               if (vrcholy[akt + 2][akt2 - 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 - 1] == -1) {
+                  vrcholy[akt + 2][akt2 - 1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+2, akt2-1), vrcholy[akt][akt2] + 1);
+               }
+            if (akt - 1 > 0 && akt2 +2 <= b)
+               if (vrcholy[akt - 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt - 1][akt2 + 2] == -1) {
+                  vrcholy[akt - 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-1, akt2+2), vrcholy[akt][akt2] + 1);
+               }
+            if (akt - 2 > 0 && akt2 +1 <= b)
+               if (vrcholy[akt - 2][akt2 +1] > vrcholy[akt][akt2] && uz[akt - 2][akt2 +1] == -1) {
+                  vrcholy[akt - 2][akt2 +1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt-2, akt2+1), vrcholy[akt][akt2] + 1);
+               }
             if (akt + 1 <= a && akt2 + 2 <= b)
-               return 1;
-            return 0;
-}
-
-int main(void) {
-   int a, b, c, d, e, f, g, aa, i, ii, akt, akt2, j, k, tah;
-   while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) > 0) {
-      if (over(c, d, a, b) == 0) {
-         j = abs(c - e);
-         k = abs(d - f);
-         if (j + k == 0)
-            printf("0\n");
-         else
-            printf("impossible\n");
-      } else {
-         j = abs(c - e);
-         k = abs(d - f);
-         tah = 0;
-         while (j + k > 2) {
-            if (j > k) {
-               j = j - 2;
-               if (k > 0)
-                  k = k - 1;
-               else
-                  k = k + 1;
+               if (vrcholy[akt + 1][akt2 + 2] > vrcholy[akt][akt2] && uz[akt + 1][akt2 + 2] == -1) {
+                  vrcholy[akt + 1][akt2 + 2] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+1, akt2+2), vrcholy[akt][akt2] + 1);
+               }
+            if (akt + 2 <= a && akt2 + 1 <= b)
+               if (vrcholy[akt + 2][akt2 + 1] > vrcholy[akt][akt2] && uz[akt + 2][akt2 + 1] == -1) {
+                  vrcholy[akt + 2][akt2 + 1] = vrcholy[akt][akt2] + 1;
+                  heapInsert(MP(akt+2, akt2+1), vrcholy[akt][akt2] + 1);
+               }
             } else {
-               if (j > 0)
-                  j = j - 1;
-               else
-                  j = j + 1;
-               k = k - 2;
+               ok = 0;
             }
-            tah++;
-         }
-         if (j == 1 && k == 1)
-            tah = tah + 2;
-         if (j + k == 1)
-            tah = tah + 3;
-         if ((j == 0 && k == 2) || (j == 2 && k == 0))
-            tah = tah + 2;
-         printf("%d\n", tah);
       }
+      if (vrcholy[e][f] != 9999999)
+         printf("%d\n", vrcholy[e][f]);
+      else
+         printf("impossible\n");
    }
+
+
    return 0;
 }