Source code for submission s994

Go to diff to previous submission

fms.cpp

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <limits.h>
  8. #include <map>
  9. #include <queue>
  10. #include <vector>
  11. #include <set>
  12. #include <stack>
  13. #include <bitset>
  14. #include <string>
  15.  
  16. using namespace std;
  17.  
  18. typedef pair<int,int> ii;
  19. typedef vector<int> vi;
  20. typedef vector<ii> vii;
  21. typedef set<int> si;
  22. typedef set<ii> sii;
  23.  
  24. #define MP make_pair
  25. #define PB push_back
  26. #define REP(i,a) for ( int i = 0; i < int(a); i++)
  27. #define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++)
  28. #define FORD(i,a,b) for(int i= int(a); i>=int(b); i--)
  29.  
  30. const int INF = 1<<29;
  31. typedef long long int ll;
  32.  
  33. int ar, ac, tr, tc;
  34. char board[1001][1001];
  35. int tiles[1001][1001];
  36.  
  37. int isIn( int r1, int r2, int c1, int c2 )
  38. {
  39. int count = 0;
  40. r1 = max( r1, 0 );
  41. r2 = min( r2, ar - 1 );
  42. c1 = max( c1, 0 );
  43. c2 = min( c2, ac - 1 );
  44. //printf("%d %d %d %d\n", r1, r2, c1, c2);
  45. FOR( i, r1, r2 )
  46. FOR( j, c1, c2 )
  47. if ( board[i][j] == 'X' )
  48. ++count;
  49. return count;
  50. }
  51.  
  52. void updateTile( int r1, int r2, int c1, int c2, int x, int y )
  53. {
  54. r1 = max( r1, 0 );
  55. r2 = min( r2, ar - 1 );
  56. c1 = max( c1, 0 );
  57. c2 = min( c2, ac - 1 );
  58. if ( c1 > 0 )
  59. FOR( i, r1, r2 )
  60. if ( board[i][c1-1] == 'X' )
  61. --tiles[x][y];
  62. if (c2 <=ac-1 )
  63. FOR( i, r1, r2 )
  64. if ( board[i][c2] == 'X' )
  65. ++tiles[x][y];
  66. }
  67.  
  68. void updateTile2( int r1, int r2, int c1, int c2, int x, int y )
  69. {
  70. r1 = max( r1, 0 );
  71. r2 = min( r2, ar - 1 );
  72. c1 = max( c1, 0 );
  73. c2 = min( c2, ac - 1 );
  74. if ( c1 >= 0 )
  75. FOR( i, r1, r2 )
  76. if ( board[i][c1] == 'X' )
  77. ++tiles[x][y];
  78. if (c2 <ac-1 )
  79. FOR( i, r1, r2 )
  80. if ( board[i][c2+1] == 'X' )
  81. --tiles[x][y];
  82. }
  83.  
  84.  
  85.  
  86. int countTiles( int r, int c, bool left )
  87. {
  88. int count = 0;
  89. for ( int i = r, i2=0; i < ar; i += tr, i2++ ) {
  90. for ( int j = c, j2=0; j < ac; j += tc, j2++ ) {
  91. if(!left)
  92. updateTile(i,i+tr-1,j,j+tc-1,i2,j2);
  93. else
  94. updateTile2(i,i+tr-1,j,j+tc-1,i2,j2);
  95. if ( tiles[i2][j2] >0 )
  96. ++count;
  97. }
  98.  
  99. }
  100. return count;
  101. }
  102.  
  103. int prepare( int r, int c )
  104. { int sum = 0;
  105. int i2 = 0, j2;
  106. for ( int i = r; i < ar; i += tr, ++i2 )
  107. {
  108. j2 = 0;
  109. for ( int j = c; j < ac; j += tc, ++j2 ) {
  110. tiles[i2][j2] = isIn( i, i+tr-1, j, j+tc-1 );
  111. if ( tiles[i2][j2] >0 ) sum++;
  112. }
  113. }
  114. return sum;
  115. }
  116. /*
  117. void updateRow(int r){
  118.   for (int i2=0 ; r < ar; r += tr, ++i2 )
  119.   {
  120.   for ( int j = -tc+1, j2=0; j < ac; j += tc, ++j2 )
  121.   tiles[i2][j2] = c
  122.   }
  123. }*/
  124.  
  125.  
  126. int main()
  127. {
  128. while ( scanf("%d%d%d%d", &ar, &ac, &tr, &tc) == 4 )
  129. {
  130. FOR( i, 0, ar-1 )
  131. {
  132. FOR( j, 0, ac-1 )
  133. scanf(" %c", &board[i][j]);
  134. //scanf("%*c");
  135. }
  136. int count = INT_MAX;
  137. int tmp;
  138. //prepare( -tr+1, -tc+1 );
  139. FOR( i, -tr+1, 0 )
  140. {
  141. tmp = prepare(i,-tc+1);
  142. count = min( count, tmp );
  143. FOR( j, -tc+2, 0 )
  144. {
  145. //if ( i == -tr+1 && j == -tc+1 )
  146. // continue;
  147. tmp = countTiles( i, j,0 );
  148. count = min( count, tmp );
  149. //printf("%d-%d\n", tmp, count);
  150. }
  151. // updateRow(i);
  152. /* ++i;
  153. if ( i >= 0 )
  154. break;
  155.   prepare(i,-tc+1);
  156. FORD( j, 0, -tc+1 )
  157. {
  158. if ( i == -tr+1 && j == -tc+1 )
  159. continue;
  160. int tmp = countTiles( i, j,1 );
  161.   count = min( count, tmp );
  162. //printf("%d-%d\n", tmp, count);
  163. }*/
  164. }
  165. printf("%d\n", count);
  166. // break;
  167. }
  168. return 0;
  169. }
  170.  
  171.  

Diff to submission s979

fms.cpp

--- c5.s979.cteam013.fm.cpp.0.fms.cpp
+++ c5.s994.cteam013.fm.cpp.0.fms.cpp
@@ -101,13 +101,16 @@
 }
 
-void prepare( int r, int c )
-{
+int prepare( int r, int c )
+{        int sum = 0;
         int i2 = 0, j2;
         for ( int i = r; i < ar; i += tr, ++i2 )
         {
                 j2 = 0;
-                for ( int j = c; j < ac; j += tc, ++j2  )
+                for ( int j = c; j < ac; j += tc, ++j2  ) {
                         tiles[i2][j2] = isIn( i, i+tr-1, j, j+tc-1 );
+                         if ( tiles[i2][j2] >0 ) sum++;
+                }
         }
+   return sum;
 }
 /*
@@ -132,16 +135,18 @@
                 }
                 int count = INT_MAX;
+                int tmp;
                 //prepare( -tr+1, -tc+1 );
                 FOR( i, -tr+1, 0 )
                 {
-                     prepare(i,-tc+1);
-                        FOR( j, -tc+1, 0 )
-                        {
-                                if ( i == -tr+1 && j == -tc+1 )
-                                        continue;
-                                int tmp = countTiles( i, j,0 );
-        count = min( count, tmp );
+                   tmp = prepare(i,-tc+1);
+                   count = min( count, tmp );
+                   FOR( j, -tc+2, 0 )
+                   {
+                        //if ( i == -tr+1 && j == -tc+1 )
+                        //  continue;
+                        tmp = countTiles( i, j,0 );
+                        count = min( count, tmp );
                                 //printf("%d-%d\n", tmp, count);
-                        }
+                   }
        //           updateRow(i);
 /*                      ++i;