oj.uz

답안 #107834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107834 2019-04-26T02:00:06 Z cki86201 흑백 이미지 찾기 (kriii3_G) C++11
68 / 101
 8198 ms 442564 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);
		if(A[i][j] < 0) return 0;
	}
	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:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A[i] + j);
   ~~~~~^~~~~~~~~~~~~~~~
G.cpp:139: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:140: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 8336 KB Output is correct
2 Correct 83 ms 8364 KB Output is correct
3 Correct 101 ms 8344 KB Output is correct
4 Correct 102 ms 8464 KB Output is correct
5 Correct 96 ms 8312 KB Output is correct
6 Correct 99 ms 8440 KB Output is correct
7 Correct 91 ms 8312 KB Output is correct
8 Correct 87 ms 8312 KB Output is correct
9 Correct 88 ms 8312 KB Output is correct
10 Correct 100 ms 8476 KB Output is correct
11 Correct 114 ms 8312 KB Output is correct
12 Correct 105 ms 8312 KB Output is correct
13 Correct 87 ms 8312 KB Output is correct
14 Correct 94 ms 8464 KB Output is correct
15 Correct 108 ms 8464 KB Output is correct
16 Correct 93 ms 8312 KB Output is correct
17 Correct 94 ms 8440 KB Output is correct
18 Correct 84 ms 8312 KB Output is correct
19 Incorrect 3 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
68.0 / 68.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8063 ms 436924 KB Output is correct
2 Correct 7449 ms 435252 KB Output is correct
3 Correct 7706 ms 435776 KB Output is correct
4 Correct 7779 ms 435252 KB Output is correct
5 Correct 7948 ms 435772 KB Output is correct
6 Correct 7552 ms 435784 KB Output is correct
7 Correct 7880 ms 435868 KB Output is correct
8 Correct 7801 ms 435740 KB Output is correct
9 Correct 7783 ms 435776 KB Output is correct
10 Correct 7798 ms 435904 KB Output is correct
11 Correct 8198 ms 435884 KB Output is correct
12 Correct 7918 ms 435768 KB Output is correct
13 Correct 7174 ms 435904 KB Output is correct
14 Correct 8096 ms 435772 KB Output is correct
15 Correct 8129 ms 435904 KB Output is correct
16 Correct 7348 ms 440500 KB Output is correct
17 Correct 7391 ms 440520 KB Output is correct
18 Correct 7043 ms 440792 KB Output is correct
19 Correct 7170 ms 440560 KB Output is correct
20 Correct 7585 ms 440564 KB Output is correct
21 Correct 7134 ms 440600 KB Output is correct
22 Correct 7353 ms 442564 KB Output is correct
23 Correct 7338 ms 440628 KB Output is correct
24 Correct 7437 ms 440592 KB Output is correct
25 Correct 7672 ms 440564 KB Output is correct
26 Correct 7628 ms 438880 KB Output is correct
27 Correct 7530 ms 440520 KB Output is correct
28 Correct 7833 ms 435940 KB Output is correct
29 Correct 7928 ms 435188 KB Output is correct
30 Correct 7922 ms 434652 KB Output is correct
31 Correct 7343 ms 434620 KB Output is correct
32 Correct 7361 ms 440452 KB Output is correct