| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 637843 |
2022-09-03T12:02:36 Z |
TAMREF |
흑백 이미지 찾기 (kriii3_G) |
C++17 |
|
10000 ms |
8844 KB |
#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
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);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
468 KB |
Output is correct |
| 2 |
Correct |
6 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
464 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2749 ms |
8752 KB |
Output is correct |
| 2 |
Correct |
8622 ms |
8844 KB |
Output is correct |
| 3 |
Execution timed out |
10030 ms |
8836 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
