Source code for submission s939

Go to diff to previous submission

#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <bitset>
#include <string>
 
using namespace std;
 
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef set<int> si;
typedef set<ii> sii;
 
#define MP make_pair
#define PB push_back
#define REP(i,a) for ( int i = 0; i < int(a); i++)
#define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++)
#define FORD(i,a,b) for(int i= int(a); i>=int(b); i--)
 
const int INF = 1<<29;
typedef long long int ll;
 
int  ar, ac, tr, tc;
char board[1001][1001];
int  tiles[1001][1001];
 
int isIn( int r1, int r2, int c1, int c2 )
{
	int count = 0;
	r1 = max( r1, 0 );
	r2 = min( r2, ar - 1 );
	c1 = max( c1, 0 );
	c2 = min( c2, ac - 1 );
	//printf("%d %d %d %d\n", r1, r2, c1, c2);
	FOR( i, r1, r2 )
		FOR( j, c1, c2 ) 
			if ( board[i][j] == 'X' )
				++count;
	return count;
}
 
void updateTile( 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-1] == 'X' )
				--tiles[x][y];
        if (c2 <=ac-1 )
	FOR( i, r1, r2 ) 
		if ( board[i][c2] == 'X' )
			++tiles[x][y];
}
 
int countTiles( int r, int c )
{
	int count = 0;
	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 ( tiles[i2][j2] >0 ) 
                   ++count;
                } 
  return count;
}
 
void prepare( int r, int c )
{
	int i2 = 0, j2;
	for ( int i = r; i < ar; i += tr, ++i2 )
	{
		j2 = 0;
		for ( int j = c; j < ac; j += tc, ++j2  )
			tiles[i2][j2] = isIn( i, i+tr-1, j, j+tc-1 );
	}
}
 
int main()
{
	while ( scanf("%d%d%d%d", &ar, &ac, &tr, &tc) == 4 )
	{
		FOR( i, 0, ar-1 )
		{
			FOR( j, 0, ac-1 )
				scanf(" %c", &board[i][j]);
			//scanf("%*c");
		}
		int count = INT_MAX;
		prepare( -tr+1, -tc+1 );
		FOR( i, -tr+1, 0 )
		{
			FOR( j, -tc+1, 0 )
			{
				if ( i == -tr+1 && j == -tc+1 )
					continue;
				int tmp = countTiles( i, j );
        count = min( count, tmp );
				//printf("%d-%d\n", tmp, count);
			}
			++i;
			if ( i >= 0 )
				break;
			FORD( j, 0, -tc+1 )
			{
				if ( i == -tr+1 && j == -tc+1 )
					continue;
				int tmp = countTiles( i, j );
        count = min( count, tmp );
				//printf("%d-%d\n", tmp, count);
			}
		}
		printf("%d\n", count);
	//	break;
	}
	return 0;
}
 
 

Diff to submission s878

--- c5.s878.cteam013.fm.cpp.0.fm.cpp
+++ c5.s939.cteam013.fm.cpp.0.fms.cpp
@@ -33,7 +33,9 @@
 int  ar, ac, tr, tc;
 char board[1001][1001];
+int  tiles[1001][1001];
 
-bool isIn( int r1, int r2, int c1, int c2 )
+int isIn( int r1, int r2, int c1, int c2 )
 {
+        int count = 0;
         r1 = max( r1, 0 );
         r2 = min( r2, ar - 1 );
@@ -44,6 +46,22 @@
                 FOR( j, c1, c2 ) 
                         if ( board[i][j] == 'X' )
-                                return true;
-        return false;
+                                ++count;
+        return count;
+}
+
+void updateTile( 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-1] == 'X' )
+                                --tiles[x][y];
+        if (c2 <=ac-1 )
+        FOR( i, r1, r2 ) 
+                if ( board[i][c2] == 'X' )
+                        ++tiles[x][y];
 }
 
@@ -51,11 +69,22 @@
 {
         int count = 0;
-        for ( int i = r; i < ar; i += tr )
-                for ( int j = c; j < ac; j += tc )
-                        if ( isIn( i, i+tr-1, j, j+tc-1 ) ) {
-                                ++count;
-        //printf("YEP\n");
-      }
-        return count;
+        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 ( tiles[i2][j2] >0 ) 
+                   ++count;
+                } 
+  return count;
+}
+
+void prepare( int r, int c )
+{
+        int i2 = 0, j2;
+        for ( int i = r; i < ar; i += tr, ++i2 )
+        {
+                j2 = 0;
+                for ( int j = c; j < ac; j += tc, ++j2  )
+                        tiles[i2][j2] = isIn( i, i+tr-1, j, j+tc-1 );
+        }
 }
 
@@ -71,11 +100,27 @@
                 }
                 int count = INT_MAX;
+                prepare( -tr+1, -tc+1 );
                 FOR( i, -tr+1, 0 )
+                {
                         FOR( j, -tc+1, 0 )
                         {
+                                if ( i == -tr+1 && j == -tc+1 )
+                                        continue;
+                                int tmp = countTiles( i, j );
+        count = min( count, tmp );
+                                //printf("%d-%d\n", tmp, count);
+                        }
+                        ++i;
+                        if ( i >= 0 )
+                                break;
+                        FORD( j, 0, -tc+1 )
+                        {
+                                if ( i == -tr+1 && j == -tc+1 )
+                                        continue;
                                 int tmp = countTiles( i, j );
         count = min( count, tmp );
                                 //printf("%d-%d\n", tmp, count);
                         }
+                }
                 printf("%d\n", count);
         //      break;