Submission #15413

#	Time	Username	Problem	Language	Result	Execution time	Memory
15413		xhae	흑백 이미지 찾기 (kriii3_G)	C++14	101 / 101	214 ms	33096 KiB

G

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int trial = 2;
//const int range = 65537;
const int max_n = 1000;

int mult[trial][max_n][max_n];
long long mult_sum_A[trial][max_n+4][max_n+4];
long long mult_sum_B[trial];
int A[max_n][max_n];
int B[max_n][max_n];

int main()
{
  int N, M;
  scanf("%d %d", &N, &M);
  for (int i=0; i<N; i++)
    for (int j=0; j<M; j++)
      scanf("%d", &A[i][j]);

  int R, C;
  scanf("%d %d", &R, &C);
  bool all_same = true;
  int py = -1, px = -1;
  for (int i=0; i<R; i++)
    for (int j=0; j<C; j++) {
      scanf("%d", &B[i][j]);
      if (B[i][j] != B[0][0]) {
        all_same = false;
        py = i;
        px = j;
      }
    }
  if (all_same) {
    printf("%d\n", (N-R+1) * (M-C+1));
    return 0;
  }

  // no srand is deliberate...
  for (int i=0; i<N; i++)
    for (int j=0; j<M; j++) {
      mult[0][i][j] = 1;
      mult[1][i][j] = i+j;
    }
  for (int i=0; i<trial; i++) {
    for (int j=0; j<N; j++)
      for (int k=0; k<M; k++)
        mult_sum_A[i][j+1][k+1] = mult_sum_A[i][j+1][k] + mult_sum_A[i][j][k+1] - mult_sum_A[i][j][k] + 1LL * mult[i][j][k] * A[j][k];
    for (int j=0; j<R; j++)
      for (int k=0; k<C; k++)
        mult_sum_B[i] += 1LL * mult[i][j][k] * B[j][k];
  }

  int res = 0;
  for (int sy=0; sy<N-R+1; sy++)
    for (int sx=0; sx<M-C+1; sx++) {
      if (A[sy][sx] == A[sy+py][sx+px]) continue;

      long long R0 = mult_sum_A[0][sy+R][sx+C] - mult_sum_A[0][sy][sx+C] - mult_sum_A[0][sy+R][sx] + mult_sum_A[0][sy][sx];
      long long R1 = mult_sum_A[1][sy+R][sx+C] - mult_sum_A[1][sy][sx+C] - mult_sum_A[1][sy+R][sx] + mult_sum_A[1][sy][sx];
      R1 -= (sy + sx) * R0;

      __int128_t dim = R*C;
      if ((A[sy+py][sx+px]*dim - A[sy][sx]*dim) * (__int128_t)(mult_sum_B[0] - B[py][px]*dim) !=
          (B[py][px]*dim - B[0][0]*dim) * (__int128_t)(R0 - A[sy+py][sx+px]*dim)) continue;

      if (dim > 0) {
        __int128_t dim2 = dim * (R+C-2) / 2;
        if ((A[sy+py][sx+px]*dim2 - A[sy][sx]*dim2) * (__int128_t)(mult_sum_B[1] - B[py][px]*dim2) !=
            (B[py][px]*dim2 - B[0][0]*dim2) * (__int128_t)(R1 - A[sy+py][sx+px]*dim2)) continue;
      }

      res ++;
    }

  printf("%d\n", res);
}

• Subtask 1: 33 / 33
• Subtask 2: 68 / 68