Submission #637843

#	Time	Username	Problem	Language	Result	Execution time	Memory
637843		TAMREF	흑백 이미지 찾기 (kriii3_G)	C++17	0 / 101	10030 ms	8844 KiB

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[4] = {1000000007, 1000000009, 998244353, 7 << 26 | 1};

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];
            }
        }
        debug("asum = %lld\n", ll(asum));
        bool flag = true;
        for(const ll mod : tmods) {
            auto pw = [&](ll x, ll n) -> ll {
                ll r = 1, p = x;
                for(;n;n>>=1) {
                if(n&1) r = r * p % mod;
                p = p * p % mod;
                }
                return r;
            };
            auto multInv = [&](ll x) -> ll {
                return pw(x, mod - 2);
            };
            auto normalize = [&](ll x) -> ll {
                x += mod;
                return x >= mod ? x - mod : x;
            };
            ll _a = asum % mod, _b = bsum % mod, _a2 = a2sum % mod, _b2 = b2sum % mod, _ab = absum % mod;
            ll rcinv = multInv(r * c), rcinv2 = rcinv * rcinv % mod;
            ll bvar = normalize((_b2 * rcinv - _b * _b % mod * rcinv2) % mod);
            ll cov = normalize((_ab % mod * rcinv - _a * _b % mod * rcinv2) % mod);
            ll avar = normalize((_a2 * rcinv - _a * _a % mod * rcinv2) % mod);
            ll diff = normalize((cov * cov - avar * bvar) % mod);
            if(diff) {
                debug("i = %d, j = %d, mod = %lld, diff = %lld\n", i, j, mod, diff);
                flag = false;
                break;
            }
        }
        if(flag) ++ans;
    }
  }
  cout << ans << '\n';
}

Compilation message (stderr)

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);
      |         ^~~~~
G.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
G.cpp:66:9: note: in expansion of macro 'debug'
   66 |         debug("asum = %lld\n", ll(asum));
      |         ^~~~~
G.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
G.cpp:91:17: note: in expansion of macro 'debug'
   91 |                 debug("i = %d, j = %d, mod = %lld, diff = %lld\n", i, j, mod, diff);
      |                 ^~~~~

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