Source code for submission s896

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

Diff to submission s845

fm.cpp

--- c5.s845.cteam032.fm.cpp.0.fm.cpp
+++ c5.s896.cteam032.fm.cpp.0.fm.cpp
@@ -1,47 +1,2 @@
-/*
-5 5 3 1
-.....
-.X...
-.XXX.
-.XXX.
-.XXX.
-5 10 2 3
-.......XX.
-.X....XX..
-.XXX......
-.XXX......
-.XXX......
-3 3 3 3
-XXX
-XXX
-XXX
-3 3 2 2
-XXX
-XXX
-XXX
-3 3 2 2
-XX.
-XXX
-XXX
-17 32 5 9
-........XXXXXXXX................
-........XXXXXXXX................
-........XXXXXXXX................
-........XXXXXXXXX...............
-........XXXXXXXXXXXXXXX.........
-........XXXXXXXXXXXXXXXXXXXX....
-........XXXXXXXXXXXXXXXXXXXXX...
-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
-..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
-....XXXXXXXXXXXXXXXXXXXXXXXXXXX.
-......XXXXXXXXXXXXXXXXXXXXXXXXX.
-........XX..XXXXXXXXXXXXXXXXX...
-.............XXXXXXXXXXXXXX.....
-...............XXXXXXXXX........
-................XXXXXXX.........
-.................XXXXX..........
-....................XXX.........
- */
-
 #include <cstdio>
 #include <cstdlib>
@@ -63,5 +18,5 @@
 void blackhole(...) {}
 
-#define MAXN 3000
+#define MAXN 2000
 
 int Ar,Ac,Tr,Tc;
@@ -87,5 +42,5 @@
                 }
         }
-        for (int c = -Tc; c < Ac + Ac; c++) {
+        for (int c = -Tc; c < Ac + Tc; c++) {
                 for (int r = -Tr; r < Ar + Ar; r++) {
                         Q[r+Tr+1][c+Tc] += Q[r+Tr][c+Tc] + P[r+Tr+Tr][c+Tc] - P[r+Tr][c+Tc];
@@ -102,4 +57,5 @@
         debug("dx=%d dy=%d => ", dx,dy);
         for (int qx = -dx; qx < Ar; qx+=Tr) {
+                int min=-1, max=-1;
                 for (int qy = -dy; qy < Ac; qy+=Tc) {
                         if (!free_tile(qx,qy)) {