Source code for submission s825

Go to diff to previous submission

fm.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <string>
  7. #include <deque>
  8. #include <list>
  9. #include <map>
  10. #include <queue>
  11. #include <set>
  12. #include <stack>
  13. #include <vector>
  14. using namespace std;
  15.  
  16. //#define debug printf
  17. #define debug blackhole
  18. void blackhole(...) {}
  19.  
  20. int Ar,Ac,Tr,Tc;
  21. bool TAKEN[2000][2000]; // [Ar][Ac]
  22.  
  23. int P[2000][2000]; // !!! od -Tr, -Tc do Ar, Ac
  24. int Q[2000][2000];
  25.  
  26. inline int is_taken(int x, int y) {
  27. 	if (x < 0 || y < 0 || x >= Ar || y >= Ac) return 0;
  28. 	return TAKEN[x][y] ? 1 : 0;
  29. }
  30.  
  31. void build() {
  32. 	for (int i=0;i<2000;i++) {
  33. 		for (int j=0;j<2000;j++) {
  34. 			P[i][j] = 0; Q[i][j] = 0;
  35. 		}
  36. 	}
  37. 	for (int r = -Tr; r < Ar + Tr; r++){
  38. 		for (int c = -Tc; c < Ac + Tc; c++) {
  39. 			P[r+Tr][c+Tc+1] += P[r+Tr][c+Tc] + is_taken(r, c + Tc) - is_taken(r, c);
  40. 		}
  41. 	}
  42. 	for (int c = -Tc; c < Ac + Ac; c++) {
  43. 		for (int r = -Tr; r < Ar + Ar; r++) {
  44. 			Q[r+Tr+1][c+Tc] += Q[r+Tr][c+Tc] + P[r+Tr+Tr][c+Tc] - P[r+Tr][c+Tc];
  45. 		}
  46. 	}
  47. }
  48.  
  49. bool free_tile(int sx, int sy) {
  50. 	return Q[sx+Tr][sy+Tc] == 0;
  51. }
  52.  
  53. long tiles_needed_for(int dx, int dy) {
  54. 	long taken = 0;
  55. 	debug("dx=%d dy=%d => ", dx,dy);
  56. 	for (int qx = -dx; qx < Ar; qx+=Tr) {
  57. 		for (int qy = -dy; qy < Ac; qy+=Tc) {
  58. 			if (!free_tile(qx,qy)) {
  59. 				taken += 1;
  60. 				debug("(%d,%d) ", qx,qy);
  61. 			}
  62. 		}
  63. 	}
  64. 	debug(" ---> %ld\n", taken);
  65. 	return taken;
  66. }
  67.  
  68. void debug_R_Q() {
  69. 	debug("vstup: \n");
  70. 	for (int r=-Tr; r<Ar+Tr; r++) {
  71. 		for (int c = -Tc; c<Ac+Tc; c++) {
  72. 			debug(" %c ", is_taken(r,c) ? 'X' : '.');
  73. 		}
  74. 		debug("\n");
  75. 	}
  76. 	debug("\n");
  77.  
  78. 	debug("P: \n");
  79. 	for (int r=-Tr; r<Ar+Tr; r++) {
  80. 		for (int c = -Tc; c<Ac+Tc; c++) {
  81. 			if (!P[r+Tr][c+Tc]) {
  82. 				debug(" . ");
  83. 			} else {
  84. 				debug("%02d ", P[r+Tr][c+Tc]);
  85. 			}
  86. 		}
  87. 		debug("\n");
  88. 	}
  89. 	debug("\n");
  90.  
  91. 	debug("Q: \n");
  92. 	for (int r=-Tr; r<Ar+Tr; r++) {
  93. 		for (int c = -Tc; c<Ac+Tc; c++) {
  94. 			if (!Q[r+Tr][c+Tc]) {
  95. 				debug(" . ");
  96. 			} else {
  97. 				debug("%02d ", Q[r+Tr][c+Tc]);
  98. 			}
  99. 		}
  100. 		debug("\n");
  101. 	}
  102. 	debug("\n");
  103. }
  104.  
  105. void solve() {
  106. 	build();
  107. 	debug_R_Q();
  108. 	long best = -1;
  109. 	for (int dx = 0; dx < Tr; dx++) {
  110. 		for (int dy = 0; dy < Tc; dy++) {
  111. 			long tiles = tiles_needed_for(dx, dy);
  112. 			if (best == -1 || best > tiles) {
  113. 				best = tiles;
  114. 			}
  115. 		}
  116. 	}
  117. 	printf("%ld\n", best);
  118. }
  119.  
  120. int main() {
  121. 	while (true) {
  122. 		if (scanf("%d%d%d%d",&Ar,&Ac,&Tr,&Tc) != 4) break;
  123. 		for (int i = 0; i < Ar; i++) {
  124. 			char line[10000];
  125. 			scanf("%s", line);
  126. 			for (int j=0;j<Ac;j++) {
  127. 				TAKEN[i][j] = line[j] == 'X';
  128. 			}
  129. 		}
  130. 		solve();
  131. 	}
  132. 	return 0;
  133. }
  134.  

Diff to submission s816

fm.cpp

--- c5.s816.cteam032.fm.cpp.0.fm.cpp
+++ c5.s825.cteam032.fm.cpp.0.fm.cpp
@@ -79,5 +79,9 @@
         for (int r=-Tr; r<Ar+Tr; r++) {
                 for (int c = -Tc; c<Ac+Tc; c++) {
-                        debug("%02d ", P[r][c]);
+                        if (!P[r+Tr][c+Tc]) {
+                                debug(" . ");
+                        } else {
+                                debug("%02d ", P[r+Tr][c+Tc]);
+                        }
                 }
                 debug("\n");
@@ -88,5 +92,9 @@
         for (int r=-Tr; r<Ar+Tr; r++) {
                 for (int c = -Tc; c<Ac+Tc; c++) {
-                        debug("%02d ", Q[r][c]);
+                        if (!Q[r+Tr][c+Tc]) {
+                                debug(" . ");
+                        } else {
+                                debug("%02d ", Q[r+Tr][c+Tc]);
+                        }
                 }
                 debug("\n");
@@ -100,5 +108,5 @@
         long best = -1;
         for (int dx = 0; dx < Tr; dx++) {
-                for (int dy = 0; dy < Tr; dy++) {
+                for (int dy = 0; dy < Tc; dy++) {
                         long tiles = tiles_needed_for(dx, dy);
                         if (best == -1 || best > tiles) {