oj.uz

Submission #107833

# Submission time Handle Problem Language Result Execution time Memory
107833 2019-04-26T01:58:35 Z cki86201 흑백 이미지 찾기 (kriii3_G) C++11
101 / 101
 9096 ms 443624 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 = 8;
		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()+(A[i].real()>0?0.5:-0.5)));
        	ll g2=((ll)(A[i].imag()+(A[i].imag()>0?0.5:-0.5)));
        	ll g3=((ll)(B[i].real()+(B[i].real()>0?0.5:-0.5)));
        	ll g4=((ll)(B[i].imag()+(B[i].imag()>0?0.5:-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)];
		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:130: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:131: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:136: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:137: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 79 ms 8184 KB Output is correct
2 Correct 82 ms 8268 KB Output is correct
3 Correct 88 ms 8184 KB Output is correct
4 Correct 78 ms 8312 KB Output is correct
5 Correct 102 ms 8304 KB Output is correct
6 Correct 88 ms 8284 KB Output is correct
7 Correct 84 ms 8308 KB Output is correct
8 Correct 80 ms 8312 KB Output is correct
9 Correct 81 ms 8312 KB Output is correct
10 Correct 92 ms 8312 KB Output is correct
11 Correct 81 ms 8312 KB Output is correct
12 Correct 87 ms 8364 KB Output is correct
13 Correct 105 ms 8312 KB Output is correct
14 Correct 88 ms 8312 KB Output is correct
15 Correct 85 ms 8340 KB Output is correct
16 Correct 88 ms 8184 KB Output is correct
17 Correct 86 ms 8184 KB Output is correct
18 Correct 94 ms 8184 KB Output is correct
19 Correct 97 ms 8292 KB Output is correct
20 Correct 85 ms 8312 KB Output is correct
21 Correct 115 ms 8312 KB Output is correct
22 Correct 89 ms 8420 KB Output is correct
23 Correct 95 ms 8388 KB Output is correct
24 Correct 87 ms 8312 KB Output is correct
25 Correct 98 ms 8440 KB Output is correct
26 Correct 90 ms 8440 KB Output is correct
27 Correct 85 ms 8344 KB Output is correct
28 Correct 86 ms 8312 KB Output is correct
29 Correct 92 ms 8356 KB Output is correct
30 Correct 75 ms 8312 KB Output is correct
31 Correct 88 ms 8508 KB Output is correct
32 Correct 79 ms 8232 KB Output is correct

Subtask #2
68.0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 8235 ms 434848 KB Output is correct
2 Correct 9096 ms 437284 KB Output is correct
3 Correct 7846 ms 437808 KB Output is correct
4 Correct 8057 ms 437164 KB Output is correct
5 Correct 7915 ms 437684 KB Output is correct
6 Correct 7550 ms 437764 KB Output is correct
7 Correct 8138 ms 437712 KB Output is correct
8 Correct 7665 ms 437632 KB Output is correct
9 Correct 7852 ms 437708 KB Output is correct
10 Correct 8047 ms 437588 KB Output is correct
11 Correct 8259 ms 437536 KB Output is correct
12 Correct 8220 ms 437580 KB Output is correct
13 Correct 7234 ms 437544 KB Output is correct
14 Correct 7673 ms 437440 KB Output is correct
15 Correct 7775 ms 437536 KB Output is correct
16 Correct 7139 ms 441940 KB Output is correct
17 Correct 7674 ms 441940 KB Output is correct
18 Correct 7398 ms 442076 KB Output is correct
19 Correct 7428 ms 441932 KB Output is correct
20 Correct 7539 ms 441904 KB Output is correct
21 Correct 7418 ms 442056 KB Output is correct
22 Correct 7372 ms 443624 KB Output is correct
23 Correct 7588 ms 441732 KB Output is correct
24 Correct 7291 ms 441572 KB Output is correct
25 Correct 8053 ms 440592 KB Output is correct
26 Correct 7677 ms 438900 KB Output is correct
27 Correct 7296 ms 440468 KB Output is correct
28 Correct 7471 ms 435940 KB Output is correct
29 Correct 7477 ms 435152 KB Output is correct
30 Correct 7816 ms 434776 KB Output is correct
31 Correct 7312 ms 434608 KB Output is correct
32 Correct 7279 ms 440464 KB Output is correct