oj.uz

답안 #107831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107831 2019-04-26T01:55:33 Z cki86201 흑백 이미지 찾기 (kriii3_G) C++11
68 / 101
 8462 ms 442732 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);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(A[i][j] < 0 || A[i][j] > 65535) exit(0);
	for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) if(B[i][j] < 0 || B[i][j] > 65535) exit(0);
	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
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 8312 KB Output is correct
2 Correct 90 ms 8184 KB Output is correct
3 Correct 95 ms 8312 KB Output is correct
4 Correct 91 ms 8184 KB Output is correct
5 Correct 91 ms 8300 KB Output is correct
6 Correct 87 ms 8304 KB Output is correct
7 Correct 102 ms 8312 KB Output is correct
8 Correct 82 ms 8308 KB Output is correct
9 Correct 119 ms 8228 KB Output is correct
10 Correct 93 ms 8312 KB Output is correct
11 Correct 87 ms 8340 KB Output is correct
12 Correct 86 ms 8440 KB Output is correct
13 Correct 82 ms 8312 KB Output is correct
14 Correct 103 ms 8336 KB Output is correct
15 Correct 82 ms 8316 KB Output is correct
16 Correct 83 ms 8312 KB Output is correct
17 Correct 92 ms 8440 KB Output is correct
18 Correct 93 ms 8400 KB Output is correct
19 Incorrect 6 ms 1664 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7736 ms 434860 KB Output is correct
2 Correct 7318 ms 435252 KB Output is correct
3 Correct 7699 ms 435996 KB Output is correct
4 Correct 7631 ms 435096 KB Output is correct
5 Correct 8102 ms 435996 KB Output is correct
6 Correct 7524 ms 435912 KB Output is correct
7 Correct 7709 ms 435744 KB Output is correct
8 Correct 7502 ms 435872 KB Output is correct
9 Correct 7444 ms 435780 KB Output is correct
10 Correct 8287 ms 435784 KB Output is correct
11 Correct 7642 ms 435928 KB Output is correct
12 Correct 7830 ms 435920 KB Output is correct
13 Correct 7156 ms 435936 KB Output is correct
14 Correct 7859 ms 435968 KB Output is correct
15 Correct 7664 ms 436044 KB Output is correct
16 Correct 7862 ms 440624 KB Output is correct
17 Correct 7498 ms 440664 KB Output is correct
18 Correct 7522 ms 440704 KB Output is correct
19 Correct 7651 ms 440716 KB Output is correct
20 Correct 7629 ms 440708 KB Output is correct
21 Correct 6985 ms 440732 KB Output is correct
22 Correct 7185 ms 442732 KB Output is correct
23 Correct 7719 ms 440652 KB Output is correct
24 Correct 7683 ms 440756 KB Output is correct
25 Correct 8462 ms 441964 KB Output is correct
26 Correct 8352 ms 440212 KB Output is correct
27 Correct 7714 ms 441748 KB Output is correct
28 Correct 8208 ms 437348 KB Output is correct
29 Correct 8115 ms 436472 KB Output is correct
30 Correct 7961 ms 435984 KB Output is correct
31 Correct 7469 ms 435984 KB Output is correct
32 Correct 7266 ms 441652 KB Output is correct