oj.uz

답안 #107836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107836 2019-04-26T02:14:03 Z cki86201 흑백 이미지 찾기 (kriii3_G) C++11
101 / 101
 2579 ms 245596 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 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 & 127) == 127)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()+(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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 5120 KB Output is correct
2 Correct 28 ms 5120 KB Output is correct
3 Correct 30 ms 5212 KB Output is correct
4 Correct 27 ms 5240 KB Output is correct
5 Correct 24 ms 5112 KB Output is correct
6 Correct 37 ms 5216 KB Output is correct
7 Correct 37 ms 5240 KB Output is correct
8 Correct 28 ms 5248 KB Output is correct
9 Correct 26 ms 5248 KB Output is correct
10 Correct 28 ms 5376 KB Output is correct
11 Correct 27 ms 5240 KB Output is correct
12 Correct 26 ms 5224 KB Output is correct
13 Correct 33 ms 5240 KB Output is correct
14 Correct 25 ms 5240 KB Output is correct
15 Correct 30 ms 5248 KB Output is correct
16 Correct 28 ms 5216 KB Output is correct
17 Correct 26 ms 5120 KB Output is correct
18 Correct 23 ms 5240 KB Output is correct
19 Correct 24 ms 5248 KB Output is correct
20 Correct 24 ms 5248 KB Output is correct
21 Correct 27 ms 5292 KB Output is correct
22 Correct 26 ms 5248 KB Output is correct
23 Correct 24 ms 5248 KB Output is correct
24 Correct 28 ms 5248 KB Output is correct
25 Correct 22 ms 5240 KB Output is correct
26 Correct 26 ms 5248 KB Output is correct
27 Correct 24 ms 5244 KB Output is correct
28 Correct 24 ms 5248 KB Output is correct
29 Correct 24 ms 5248 KB Output is correct
30 Correct 24 ms 5248 KB Output is correct
31 Correct 28 ms 5112 KB Output is correct
32 Correct 25 ms 5240 KB Output is correct

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2263 ms 237976 KB Output is correct
2 Correct 2561 ms 238280 KB Output is correct
3 Correct 2350 ms 238892 KB Output is correct
4 Correct 2349 ms 238212 KB Output is correct
5 Correct 2462 ms 238896 KB Output is correct
6 Correct 2276 ms 238812 KB Output is correct
7 Correct 2202 ms 238860 KB Output is correct
8 Correct 2271 ms 238812 KB Output is correct
9 Correct 2408 ms 238812 KB Output is correct
10 Correct 2407 ms 238752 KB Output is correct
11 Correct 2384 ms 238812 KB Output is correct
12 Correct 2373 ms 238892 KB Output is correct
13 Correct 1649 ms 238812 KB Output is correct
14 Correct 2165 ms 238912 KB Output is correct
15 Correct 2382 ms 238912 KB Output is correct
16 Correct 2025 ms 243648 KB Output is correct
17 Correct 2060 ms 243620 KB Output is correct
18 Correct 1842 ms 243616 KB Output is correct
19 Correct 1842 ms 243804 KB Output is correct
20 Correct 1873 ms 243640 KB Output is correct
21 Correct 1827 ms 243676 KB Output is correct
22 Correct 1783 ms 245596 KB Output is correct
23 Correct 2104 ms 243496 KB Output is correct
24 Correct 2087 ms 243484 KB Output is correct
25 Correct 2077 ms 243620 KB Output is correct
26 Correct 2166 ms 242080 KB Output is correct
27 Correct 1981 ms 243448 KB Output is correct
28 Correct 2399 ms 239056 KB Output is correct
29 Correct 2579 ms 238256 KB Output is correct
30 Correct 2253 ms 237708 KB Output is correct
31 Correct 2095 ms 237656 KB Output is correct
32 Correct 2145 ms 243676 KB Output is correct