답안 #637856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637856	2022-09-03T12:21:55 Z	TAMREF	흑백 이미지 찾기 (kriii3_G)	C++17	0 / 101	10000 ms	8208 KB

G

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, r, c;
using L = __int128_t;
const ll tmods[5] = {1000000007, 1000000009, 998244353, 7 << 26 | 1, 1000000021};

int main(){
  fio;
  cin >> n >> m;
  auto a = vector<vector<ll>>(n, vector<ll>(m));
  for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];
  cin >> r >> c;
  auto b = vector<vector<ll>>(r, vector<ll>(c));
  for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) cin >> b[i][j];

  int ans = 0;
  L bsum = 0, b2sum = 0;
  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
        bsum += b[i][j];
        b2sum += b[i][j] * b[i][j];
    }
  }
  for(int i = 0; i + r - 1 < n; i++) {
    for(int j = 0; j + c - 1 < m; j++) {
        debug("i = %d, j = %d, ans = %d\n", i, j, ans);
        L asum = 0, a2sum = 0, absum = 0;
        for(int k = i; k < i + r; k++) {
            for(int l = j; l < j + c; l++) {
                asum += a[k][l];
                a2sum += a[k][l] * a[k][l];
                absum += a[k][l] * b[k-i][l-j];
            }
        }
        L bvar = (b2sum * r * c - bsum * bsum);
        L cov = (absum * r * c - asum * bsum);
        L avar =(a2sum * r * c - asum * asum);
        
        bool flag = true;
        for(const ll mod : tmods) {
            ll _c = (mod + cov % mod) % mod;
            ll _a = avar % mod, _b = bvar % mod;
            ll diff = (mod + (_c * _c - _a * _b) % mod) % mod;
            if(diff) {
                flag = false;
                break;
            }
        }
        if(flag) ++ans;
    }
  }
  cout << ans << '\n';
}

Compilation message

G.cpp: In function 'int main()':
G.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
G.cpp:57:9: note: in expansion of macro 'debug'
   57 |         debug("i = %d, j = %d, ans = %d\n", i, j, ans);
      |         ^~~~~

Subtask #1

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Incorrect	2 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2

0 / 68.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2175 ms	8188 KB	Output is correct
2	Correct	7318 ms	8208 KB	Output is correct
3	Execution timed out	10050 ms	8176 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-