oj.uz

답안 #107837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107837 2019-04-26T02:16:17 Z cki86201 흑백 이미지 찾기 (kriii3_G) C++11
101 / 101
 2534 ms 245616 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 = acos(-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(cos(ang), sin(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(cos(ang * j), sin(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 23 ms 5112 KB Output is correct
2 Correct 29 ms 5112 KB Output is correct
3 Correct 26 ms 5120 KB Output is correct
4 Correct 25 ms 5248 KB Output is correct
5 Correct 26 ms 5240 KB Output is correct
6 Correct 27 ms 5120 KB Output is correct
7 Correct 27 ms 5112 KB Output is correct
8 Correct 25 ms 5248 KB Output is correct
9 Correct 24 ms 5248 KB Output is correct
10 Correct 23 ms 5248 KB Output is correct
11 Correct 22 ms 5244 KB Output is correct
12 Correct 28 ms 5240 KB Output is correct
13 Correct 33 ms 5248 KB Output is correct
14 Correct 25 ms 5340 KB Output is correct
15 Correct 22 ms 5248 KB Output is correct
16 Correct 27 ms 5240 KB Output is correct
17 Correct 24 ms 5248 KB Output is correct
18 Correct 31 ms 5212 KB Output is correct
19 Correct 23 ms 5208 KB Output is correct
20 Correct 26 ms 5112 KB Output is correct
21 Correct 33 ms 5340 KB Output is correct
22 Correct 25 ms 5248 KB Output is correct
23 Correct 25 ms 5248 KB Output is correct
24 Correct 26 ms 5376 KB Output is correct
25 Correct 27 ms 5212 KB Output is correct
26 Correct 26 ms 5248 KB Output is correct
27 Correct 27 ms 5112 KB Output is correct
28 Correct 23 ms 5132 KB Output is correct
29 Correct 26 ms 5240 KB Output is correct
30 Correct 23 ms 5248 KB Output is correct
31 Correct 23 ms 5240 KB Output is correct
32 Correct 33 ms 5260 KB Output is correct

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2367 ms 237984 KB Output is correct
2 Correct 2478 ms 238300 KB Output is correct
3 Correct 2112 ms 238724 KB Output is correct
4 Correct 2185 ms 238172 KB Output is correct
5 Correct 2248 ms 238920 KB Output is correct
6 Correct 2084 ms 238812 KB Output is correct
7 Correct 2054 ms 238844 KB Output is correct
8 Correct 2335 ms 238836 KB Output is correct
9 Correct 2368 ms 238828 KB Output is correct
10 Correct 2194 ms 238912 KB Output is correct
11 Correct 2187 ms 238940 KB Output is correct
12 Correct 2129 ms 239076 KB Output is correct
13 Correct 1700 ms 238936 KB Output is correct
14 Correct 2012 ms 238940 KB Output is correct
15 Correct 2488 ms 238940 KB Output is correct
16 Correct 1786 ms 243580 KB Output is correct
17 Correct 1998 ms 243584 KB Output is correct
18 Correct 1671 ms 243792 KB Output is correct
19 Correct 1802 ms 243816 KB Output is correct
20 Correct 1795 ms 243696 KB Output is correct
21 Correct 1826 ms 243792 KB Output is correct
22 Correct 1714 ms 245616 KB Output is correct
23 Correct 1979 ms 243484 KB Output is correct
24 Correct 2016 ms 243480 KB Output is correct
25 Correct 1761 ms 243556 KB Output is correct
26 Correct 1950 ms 241852 KB Output is correct
27 Correct 1756 ms 243596 KB Output is correct
28 Correct 2210 ms 238960 KB Output is correct
29 Correct 2534 ms 238272 KB Output is correct
30 Correct 2226 ms 237660 KB Output is correct
31 Correct 1889 ms 237780 KB Output is correct
32 Correct 1801 ms 243496 KB Output is correct