Source code for submission s979

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. void prepare( int r, int c )
  104. {
  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. 	}
  112. }
  113. /*
  114. void updateRow(int r){
  115.   for (int i2=0 ; r < ar; r += tr, ++i2 )
  116.   {
  117.      for ( int j = -tc+1, j2=0; j < ac; j += tc, ++j2  )
  118.        tiles[i2][j2] = c
  119.   }
  120. }*/
  121.  
  122.  
  123. int main()
  124. {
  125. 	while ( scanf("%d%d%d%d", &ar, &ac, &tr, &tc) == 4 )
  126. 	{
  127. 		FOR( i, 0, ar-1 )
  128. 		{
  129. 			FOR( j, 0, ac-1 )
  130. 				scanf(" %c", &board[i][j]);
  131. 			//scanf("%*c");
  132. 		}
  133. 		int count = INT_MAX;
  134. 		//prepare( -tr+1, -tc+1 );
  135. 		FOR( i, -tr+1, 0 )
  136. 		{
  137.                      prepare(i,-tc+1);
  138. 			FOR( j, -tc+1, 0 )
  139. 			{
  140. 				if ( i == -tr+1 && j == -tc+1 )
  141. 					continue;
  142. 				int tmp = countTiles( i, j,0 );
  143.         count = min( count, tmp );
  144. 				//printf("%d-%d\n", tmp, count);
  145. 			}
  146.        //           updateRow(i);
  147. /*			++i;
  148. 			if ( i >= 0 )
  149. 				break;
  150.                       prepare(i,-tc+1);
  151. 			FORD( j, 0, -tc+1 )
  152. 			{
  153. 				if ( i == -tr+1 && j == -tc+1 )
  154. 					continue;
  155. 				int tmp = countTiles( i, j,1 );
  156.         count = min( count, tmp );
  157. 				//printf("%d-%d\n", tmp, count);
  158. 			}*/
  159. 		}
  160. 		printf("%d\n", count);
  161. 	//	break;
  162. 	}
  163. 	return 0;
  164. }
  165.  
  166.  

Diff to submission s939

fms.cpp

--- c5.s939.cteam013.fm.cpp.0.fms.cpp
+++ c5.s979.cteam013.fm.cpp.0.fms.cpp
@@ -66,13 +66,36 @@
 }
 
-int countTiles( int r, int c )
+void updateTile2( int r1, int r2, int c1, int c2, int x, int y )
+{
+        r1 = max( r1, 0 );
+        r2 = min( r2, ar - 1 );
+        c1 = max( c1, 0 );
+        c2 = min( c2, ac - 1 );
+        if ( c1 >= 0 )
+          FOR( i, r1, r2 )
+            if ( board[i][c1] == 'X' )
+                        ++tiles[x][y];
+        if (c2 <ac-1 )
+        FOR( i, r1, r2 )
+                if ( board[i][c2+1] == 'X' )
+                        --tiles[x][y];
+}
+
+
+
+int countTiles( int r, int c, bool left )
 {
         int count = 0;
-        for ( int i = r, i2=0; i < ar; i += tr, i2++ )
+        for ( int i = r, i2=0; i < ar; i += tr, i2++ ) {
                 for ( int j = c, j2=0; j < ac; j += tc, j2++ ) {
-                  updateTile(i,i+tr-1,j,j+tc-1,i2,j2);
+                  if(!left)
+                    updateTile(i,i+tr-1,j,j+tc-1,i2,j2);
+                  else
+                    updateTile2(i,i+tr-1,j,j+tc-1,i2,j2);
                   if ( tiles[i2][j2] >0 ) 
                    ++count;
                 } 
+  
+       }
   return count;
 }
@@ -88,4 +111,13 @@
         }
 }
+/*
+void updateRow(int r){
+  for (int i2=0 ; r < ar; r += tr, ++i2 )
+  {
+     for ( int j = -tc+1, j2=0; j < ac; j += tc, ++j2  )
+       tiles[i2][j2] = c
+  }
+}*/
+
 
 int main()
@@ -100,26 +132,29 @@
                 }
                 int count = INT_MAX;
-                prepare( -tr+1, -tc+1 );
+                //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 );
+                                int tmp = countTiles( i, j,0 );
         count = min( count, tmp );
                                 //printf("%d-%d\n", tmp, count);
                         }
-                        ++i;
+       //           updateRow(i);
+/*                      ++i;
                         if ( i >= 0 )
                                 break;
+                      prepare(i,-tc+1);
                         FORD( j, 0, -tc+1 )
                         {
                                 if ( i == -tr+1 && j == -tc+1 )
                                         continue;
-                                int tmp = countTiles( i, j );
+                                int tmp = countTiles( i, j,1 );
         count = min( count, tmp );
                                 //printf("%d-%d\n", tmp, count);
-                        }
+                        }*/
                 }
                 printf("%d\n", count);