Source code for submission s1155

Go to diff to previous submission

fm.cpp

  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. char map[1024][1024];
  5. int Ar, Ac, Tr, Tc;
  6. int width, height;
  7.  
  8. static inline int get_Cmin(){
  9. for (int c = 0; c < Ac; ++c){
  10. for (int r = 0; r < Ar; ++r){
  11. if (map[r][c] == 'X'){
  12. return c;
  13. }
  14. }
  15. }
  16. return Ar;
  17. }
  18.  
  19. static inline int get_Cmax(){
  20. for (int c = Ac - 1; c >= 0; c--){
  21. for (int r = Ar -1; r >= 0; r--){
  22. if (map[r][c] == 'X'){
  23. return c;
  24. }
  25. }
  26. }
  27. return 0;
  28. }
  29.  
  30. static inline int get_Rmax(){
  31. for (int r = Ar - 1; r >= 0; r--){
  32. for (int c = Ac - 1; c >= 0; c--){
  33. if (map[r][c] == 'X'){
  34. return r;
  35. }
  36. }
  37. }
  38. return 0;
  39. }
  40.  
  41. static inline int get_Rmin(){
  42. for (int r = 0; r < Ar; r++){
  43. for (int c = 0; c < Ac; c++){
  44. if (map[r][c] == 'X'){
  45. return r;
  46. }
  47. }
  48. }
  49. return Ac;
  50. }
  51.  
  52. bool checkRectangle(int c, int r, int Cmin, int Rmin) {
  53. //radek
  54. int radek = (Rmin+r*Tr >= 0)? Rmin+r*Tr : 0;
  55. int sloupec = (Cmin+(c+1)*Tc-1 >= 0)? Cmin+(c+1)*Tc-1 : 0;
  56. int sloupecPP = (Cmin+c*Tc >= 0)? Cmin+c*Tc : 0;
  57. for (int i = sloupecPP; i < Cmin + (c+1)*Tc; i++)
  58. {
  59. if (map[Rmin+(r+1)*Tr-1][i] == 'X' ||
  60. map[radek][i] == 'X'){
  61. return true;
  62. }
  63. }
  64. //sloupec
  65. for (int i = radek; i < Rmin+(r+1)*Tr; i++){
  66. if (map[i][Cmin+(c+1)*Tc-1] == 'X' ||
  67. map[i][sloupec] == 'X'){
  68. return true;
  69. }
  70. }
  71. return false;
  72. }
  73.  
  74. int placement_min(int Cmin, int Rmin){
  75. int res = width * height;
  76. for (int c = 0; c < width; c++){
  77. for (int r = 0; r < height; r++){
  78. if (!checkRectangle(c, r, Cmin, Rmin)){
  79. // printf("Throwing out: %d %d\n", c, r);
  80. res--;
  81. }
  82. }
  83. }
  84. return res;
  85. }
  86.  
  87.  
  88. int main(){
  89.  
  90. while (scanf("%d %d %d %d", &Ar, &Ac, &Tr, &Tc) != EOF){
  91. for (int r = 0; r < Ar; r++){
  92. memset(map[r], 0, Ac);
  93. }
  94. for (int r = 0; r < Ar; ++r){
  95. scanf("%s%*c", map[r]);
  96. }
  97. int Cmin = get_Cmin();
  98. int Cmax = get_Cmax();
  99. int Rmin = get_Rmin();
  100. int Rmax = get_Rmax();
  101.  
  102. // printf("Cmin: %d Cmax: %d Rmin: %d Rmax: %d\n", Cmin, Cmax, Rmin, Rmax);
  103.  
  104. width = (Cmax - Cmin + Tc) / Tc;
  105. height = (Rmax - Rmin + Tr) / Tr;
  106. int res = width * height;
  107.  
  108. int diff_width = width*Tc - Cmax;
  109. int diff_height = height*Tr - Rmax;
  110.  
  111. int Cmin_new = Cmin;
  112.  
  113. for (int i = 0; i < diff_width; i++){
  114. // for (int j = 0; j < diff_height; j++){
  115. int tmp = placement_min(Cmin -i, Rmin);
  116. // printf("tmp: %d\n", tmp);
  117. if (tmp < res){
  118. Cmin_new = Cmin - i;
  119. res = tmp;
  120. }
  121. // }
  122. }
  123.  
  124. for (int i = 0; i < diff_height; i++){
  125. int tmp = placement_min(Cmin_new, Rmin - i);
  126. if (tmp < res){
  127. res = tmp;
  128. }
  129. }
  130.  
  131. printf("%d\n", res);
  132. }
  133.  
  134. }
  135.  

Diff to submission s1139

fm.cpp

--- c5.s1139.cteam024.fm.cpp.0.fm.cpp
+++ c5.s1155.cteam024.fm.cpp.0.fm.cpp
@@ -112,14 +112,15 @@
                 
                 for (int i = 0; i < diff_width; i++){
-                        for (int j = 0; j < diff_height; j++){
-                                int tmp = placement_min(Cmin -i, Rmin - j);
+//                      for (int j = 0; j < diff_height; j++){
+                                int tmp = placement_min(Cmin -i, Rmin);
 //                              printf("tmp: %d\n", tmp);
                                 if (tmp < res){
+                                        Cmin_new = Cmin - i;
                                         res = tmp;
                                 }
-                        }
+                //      }
                 }
                 
-/*              for (int i = 0; i < diff_height; i++){
+                for (int i = 0; i < diff_height; i++){
                         int tmp = placement_min(Cmin_new, Rmin - i);
                         if (tmp < res){
@@ -127,5 +128,5 @@
                         }
                 }
-*/              
+                
                 printf("%d\n", res);
         }