oj.uz

답안 #15413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15413 2015-07-12T07:17:43 Z xhae 흑백 이미지 찾기 (kriii3_G) C++14
101 / 101
 214 ms 33096 KB 
#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.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33096 KB Output is correct
2 Correct 0 ms 33096 KB Output is correct
3 Correct 0 ms 33096 KB Output is correct
4 Correct 2 ms 33096 KB Output is correct
5 Correct 4 ms 33096 KB Output is correct
6 Correct 0 ms 33096 KB Output is correct
7 Correct 2 ms 33096 KB Output is correct
8 Correct 0 ms 33096 KB Output is correct
9 Correct 0 ms 33096 KB Output is correct
10 Correct 0 ms 33096 KB Output is correct
11 Correct 0 ms 33096 KB Output is correct
12 Correct 0 ms 33096 KB Output is correct
13 Correct 0 ms 33096 KB Output is correct
14 Correct 0 ms 33096 KB Output is correct
15 Correct 2 ms 33096 KB Output is correct
16 Correct 0 ms 33096 KB Output is correct
17 Correct 2 ms 33096 KB Output is correct
18 Correct 0 ms 33096 KB Output is correct
19 Correct 4 ms 33096 KB Output is correct
20 Correct 4 ms 33096 KB Output is correct
21 Correct 0 ms 33096 KB Output is correct
22 Correct 2 ms 33096 KB Output is correct
23 Correct 0 ms 33096 KB Output is correct
24 Correct 0 ms 33096 KB Output is correct
25 Correct 2 ms 33096 KB Output is correct
26 Correct 0 ms 33096 KB Output is correct
27 Correct 0 ms 33096 KB Output is correct
28 Correct 0 ms 33096 KB Output is correct
29 Correct 4 ms 33096 KB Output is correct
30 Correct 0 ms 33096 KB Output is correct
31 Correct 0 ms 33096 KB Output is correct
32 Correct 0 ms 33096 KB Output is correct

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 33096 KB Output is correct
2 Correct 137 ms 33096 KB Output is correct
3 Correct 159 ms 33096 KB Output is correct
4 Correct 140 ms 33096 KB Output is correct
5 Correct 167 ms 33096 KB Output is correct
6 Correct 118 ms 33096 KB Output is correct
7 Correct 83 ms 33096 KB Output is correct
8 Correct 69 ms 33096 KB Output is correct
9 Correct 169 ms 33096 KB Output is correct
10 Correct 152 ms 33096 KB Output is correct
11 Correct 139 ms 33096 KB Output is correct
12 Correct 165 ms 33096 KB Output is correct
13 Correct 134 ms 33096 KB Output is correct
14 Correct 132 ms 33096 KB Output is correct
15 Correct 136 ms 33096 KB Output is correct
16 Correct 143 ms 33096 KB Output is correct
17 Correct 104 ms 33096 KB Output is correct
18 Correct 90 ms 33096 KB Output is correct
19 Correct 178 ms 33096 KB Output is correct
20 Correct 167 ms 33096 KB Output is correct
21 Correct 159 ms 33096 KB Output is correct
22 Correct 214 ms 33096 KB Output is correct
23 Correct 184 ms 33096 KB Output is correct
24 Correct 172 ms 33096 KB Output is correct
25 Correct 198 ms 33096 KB Output is correct
26 Correct 149 ms 33096 KB Output is correct
27 Correct 162 ms 33096 KB Output is correct
28 Correct 167 ms 33096 KB Output is correct
29 Correct 163 ms 33096 KB Output is correct
30 Correct 167 ms 33096 KB Output is correct
31 Correct 131 ms 33096 KB Output is correct
32 Correct 144 ms 33096 KB Output is correct