oj.uz

Submission #107830

# Submission time Handle Problem Language Result Execution time Memory
107830 2019-04-26T01:47:25 Z cki86201 흑백 이미지 찾기 (kriii3_G) C++11
101 / 101
 8164 ms 442680 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

#include <complex>
typedef long double ldouble;
namespace FFT{
	// blog.myungwoo.kr/54
	typedef complex<ldouble> base;
	typedef long long ll;
	
#define sz(x) ((int)(x).size())
 
	const ldouble C_PI = acosl(-1);
 
	void fft(vector <base> &a, bool invert){
		int n = sz(a);
		for(int i=0,j=0;i<n;++i) {
			if(i>j) swap(a[i],a[j]);
			for(int k=n>>1;(j^=k)<k;k>>=1);
		}
		for (int len=2;len<=n;len<<=1){
			ldouble ang = 2*C_PI/len*(invert?-1:1);
			base wlen(cosl(ang), sinl(ang));
			for (int i=0;i<n;i+=len){
				base w(1);
				for (int j=0;j<len/2;j++){
					if((j & 31) == 31)w = base(cosl(ang * j), sinl(ang * j));	//오차가 클 경우 이 빈도를 늘린다. cos, sin 함수는 시간 부담이 있으니 주의
					base u = a[i+j], v = a[i+j+len/2]*w;
					a[i+j] = u+v;
					a[i+j+len/2] = u-v;
					w *= wlen;
				}
			}
		}
		if (invert){
			for (int i=0;i<n;i++) a[i] /= n;
		}
	}
 
	void multiply(const vector<int> &a,const vector<int> &b,vector<int> &res, const int MOD){
		vector <base> fa(all(a)), fb(all(b));
		int n = 1;
		while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
		fa.resize(n); fb.resize(n);
		fft(fa,false); fft(fb,false);
		for (int i=0;i<n;i++) fa[i] *= fb[i];
		fft(fa,true);
		res.resize(n);
		for (int i=0;i<n;i++) res[i] = ((ll)(fa[i].real()+(fa[i].real()>0?0.5:-0.5))) % MOD;
	}
 
	void multiply_big(const vector<int> &a,const vector<int> &b, vector <ll> &res){
		// 단순히 오차가 심해 구하지 못하는 경우
		// 결과값은 long long 범위 안
		int n = 1;
		while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
		vector <base> A(n), B(n);
		int L_BLOCK = 10;
		for(int i=0;i<n;i++) A[i] = (i < sz(a) ? base(a[i] & ((1<<L_BLOCK)-1), a[i] >> L_BLOCK) : base(0));
		for(int i=0;i<n;i++) B[i] = (i < sz(b) ? base(b[i] & ((1<<L_BLOCK)-1), b[i] >> L_BLOCK) : base(0));
		fft(A, false); fft(B, false);
		vector <base> f1(n), f2(n), f3(n), f4(n);
		for(int i=0;i<n;i++) {
			int j=(n-i)&(n-1);
			f2[i]=(A[i]+conj(A[j]))*base(0.5,0);
			f1[i]=(A[i]-conj(A[j]))*base(0,-0.5);
			f4[i]=(B[i]+conj(B[j]))*base(0.5,0);
			f3[i]=(B[i]-conj(B[j]))*base(0,-0.5);
		}
		for(int i=0;i<n;i++) {
			A[i]=f1[i]*f3[i]+f1[i]*f4[i]*base(0,1);
			B[i]=f2[i]*f4[i]*base(0,1)+f2[i]*f3[i];
		}
		fft(A, true); fft(B, true);
		res.resize(n);
		for(int i=0;i<n;i++) {
			ll g1=(ll)(A[i].real()+0.5);
			ll g2=(ll)(A[i].imag()+0.5);
			ll g3=(ll)(B[i].real()+0.5);
			ll g4=(ll)(B[i].imag()+0.5);
			res[i] = (g4 + ((g2+g3)<<(L_BLOCK)) + (g1<<(L_BLOCK<<1)));
		}
	}
}

int N, M, R, C;
int A[1010][1010], B[1010][1010];
ll Sx[1010][1010], Sxx[1010][1010];

vector <int> va, vb;
vector <ll> res;

ll get_s(ll T[1010][1010], int x1, int y1, int x2, int y2) {
	return T[x2][y2] - T[x2][y1-1] - T[x1-1][y2] + T[x1-1][y1-1];
}

#define i128 __int128

int main() {
	scanf("%d%d", &N, &M);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d", A[i] + j);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) {
		Sx[i][j] = Sx[i-1][j] + Sx[i][j-1] - Sx[i-1][j-1] + A[i][j];
		Sxx[i][j] = Sxx[i-1][j] + Sxx[i][j-1] - Sxx[i-1][j-1] + (ll)A[i][j] * A[i][j];
	}
	scanf("%d%d", &R, &C);
	for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) scanf("%d", B[i] + j);
	ll sy = 0, syy = 0;
	for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) {
		sy += B[i][j];
		syy += (ll) B[i][j] * B[i][j];
	}
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) va.pb(A[i][j]);
	for(int i=R;i;i--) {
		for(int j=C;j;j--) vb.pb(B[i][j]);
		rep(j, M - C) vb.pb(0);
	}
	FFT::multiply_big(va, vb, res);
	int ans = 0;
	ll prs[3] = {1000000000000000003ll, 1000000000000000009ll, 1000000000000000031ll};
	for(int i=R;i<=N;i++) for(int j=C;j<=M;j++) {
		ll sxy = res[(i-1)*M+(j-1)];
		if(N <= 100 && M <= 100) {
			sxy = 0;
			rep(a, R) rep(b, C) sxy += (ll) A[i-a][j-b] * B[R-a][C-b];
		}
		ll sx = get_s(Sx, i-R+1, j-C+1, i, j);
		ll sxx = get_s(Sxx, i-R+1, j-C+1, i, j);
		ll n = R * C;
		if((i128)sx * sx == (i128)n * sxx) {
			if((i128)sy * sy == (i128)n * syy) ++ans;
		}
		else {
			int ok = 1;
			rep(u, 3) {
				ll mod = prs[u];
				i128 val = (i128)syy * (((i128)n * sxx - (i128)sx * sx) % mod) % mod;
				val = (val - (i128) sxy * sxy % mod * n) % mod; if(val < 0) val += mod;
				val = (val - (i128) sxx * sy % mod * sy) % mod; if(val < 0) val += mod;
				val = (val + (i128) 2 * sxy * sx % mod * sy) % mod;
				if(val != 0) ok = 0;
			}
			ans += ok;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

G.cpp: In function 'void FFT::multiply(const std::vector<int>&, const std::vector<int>&, std::vector<int>&, int)':
G.cpp:71:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
   ^~~~~
G.cpp:71:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
                                         ^
G.cpp: In function 'void FFT::multiply_big(const std::vector<int>&, const std::vector<int>&, std::vector<long long int>&)':
G.cpp:84:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
   ^~~~~
G.cpp:84:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while (n < max(sz(a),sz(b))) n <<= 1; n <<= 1;
                                         ^
G.cpp: In function 'int main()':
G.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
G.cpp:129:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d", A[i] + j);
                                              ~~~~~^~~~~~~~~~~~~~~~
G.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &R, &C);
  ~~~~~^~~~~~~~~~~~~~~~
G.cpp:135:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) scanf("%d", B[i] + j);
                                              ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8440 KB Output is correct
2 Correct 113 ms 8188 KB Output is correct
3 Correct 81 ms 8184 KB Output is correct
4 Correct 86 ms 8316 KB Output is correct
5 Correct 92 ms 8312 KB Output is correct
6 Correct 89 ms 8312 KB Output is correct
7 Correct 86 ms 8312 KB Output is correct
8 Correct 89 ms 8440 KB Output is correct
9 Correct 105 ms 8336 KB Output is correct
10 Correct 96 ms 8312 KB Output is correct
11 Correct 93 ms 8312 KB Output is correct
12 Correct 91 ms 8336 KB Output is correct
13 Correct 85 ms 8308 KB Output is correct
14 Correct 93 ms 8300 KB Output is correct
15 Correct 90 ms 8336 KB Output is correct
16 Correct 90 ms 8316 KB Output is correct
17 Correct 164 ms 8268 KB Output is correct
18 Correct 99 ms 8308 KB Output is correct
19 Correct 81 ms 8212 KB Output is correct
20 Correct 86 ms 8440 KB Output is correct
21 Correct 85 ms 8312 KB Output is correct
22 Correct 84 ms 8424 KB Output is correct
23 Correct 87 ms 8392 KB Output is correct
24 Correct 85 ms 8312 KB Output is correct
25 Correct 93 ms 8456 KB Output is correct
26 Correct 84 ms 8380 KB Output is correct
27 Correct 78 ms 8308 KB Output is correct
28 Correct 88 ms 8392 KB Output is correct
29 Correct 81 ms 8312 KB Output is correct
30 Correct 76 ms 8312 KB Output is correct
31 Correct 112 ms 8312 KB Output is correct
32 Correct 85 ms 8352 KB Output is correct

Subtask #2
68.0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 7732 ms 434848 KB Output is correct
2 Correct 7565 ms 435352 KB Output is correct
3 Correct 7452 ms 435788 KB Output is correct
4 Correct 7813 ms 435420 KB Output is correct
5 Correct 7766 ms 435780 KB Output is correct
6 Correct 7570 ms 435712 KB Output is correct
7 Correct 7692 ms 435748 KB Output is correct
8 Correct 7282 ms 435980 KB Output is correct
9 Correct 7910 ms 435804 KB Output is correct
10 Correct 7728 ms 435808 KB Output is correct
11 Correct 7393 ms 435860 KB Output is correct
12 Correct 8164 ms 435788 KB Output is correct
13 Correct 7738 ms 435820 KB Output is correct
14 Correct 7347 ms 435912 KB Output is correct
15 Correct 7197 ms 435776 KB Output is correct
16 Correct 7410 ms 440468 KB Output is correct
17 Correct 7394 ms 440712 KB Output is correct
18 Correct 7465 ms 440516 KB Output is correct
19 Correct 7676 ms 440548 KB Output is correct
20 Correct 7471 ms 440684 KB Output is correct
21 Correct 7342 ms 440752 KB Output is correct
22 Correct 7166 ms 442680 KB Output is correct
23 Correct 7001 ms 440548 KB Output is correct
24 Correct 7258 ms 440476 KB Output is correct
25 Correct 7098 ms 440552 KB Output is correct
26 Correct 7066 ms 438936 KB Output is correct
27 Correct 7517 ms 440560 KB Output is correct
28 Correct 7931 ms 435956 KB Output is correct
29 Correct 7835 ms 435292 KB Output is correct
30 Correct 7390 ms 434740 KB Output is correct
31 Correct 7324 ms 434640 KB Output is correct
32 Correct 7303 ms 440596 KB Output is correct