Submission #15396

#	Time	Username	Problem	Language	Result	Execution time	Memory
15396		myungwoo	흑백 이미지 찾기 (kriii3_G)	C++14	0 / 101	532 ms	16740 KiB

G

#pragma warning(disable:4996)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
using std::swap;
using std::vector;
using std::max;

int n, m, r, c;
long long a[1000][1000];
long long b[1000][1000];


struct bigint {
	static const long long B = 1000000ll;
	static const int len = 20;
	long long a[len];
	int sign;

	bigint(long long x = 0) {
		for (int i=0; i<len; i++) a[i] = 0;
		a[0] = abs(x);
		sign = x>=0 ? 1 : -1;

		for (int i=0; i<len-1; i++) {
			a[i+1] += a[i] / B;
			a[i] %= B;
		}
	}

	bool zero()
	{
		for (int i=0; i<len; i++) if (a[i]) return false;
		return true;
	}

	bigint bigabs() { bigint res(*this); res.sign = 1; return res; }

	bigint operator + (bigint r)
	{
		if (sign == -1 && r.sign == -1) return -(-*this + -r);
		if (sign == -1) return r - -*this;
		if (r.sign == -1) return *this - r;

		bigint res;
		res.sign = 1;

		for (int i=0; i<len; i++)
			res.a[i] = a[i] + r.a[i];

		for (int i=0; i<len-1; i++) {
			res.a[i+1] += res.a[i] / B;
			res.a[i] %= B;
		}

		return res;
	}

	bigint operator - (bigint r)
	{
		if (sign == -1 && r.sign == 1) return -(-*this + r);
		if (sign == -1) return -(-*this - -r);
		if (sign == 1 && r.sign == -1) return *this + -r;
		if (bigabs() < r.bigabs()) return -(r - *this);

		bigint res;
		res.sign = 1;

		for (int i=0; i<len; i++)
			res.a[i] = a[i] - r.a[i];

		for (int i=0; i<len-1; i++) {
			while (res.a[i] < 0) {
				res.a[i] += B;
				res.a[i+1] -= 1;
			}

			res.a[i+1] += res.a[i] / B;
			res.a[i] %= B;
		}

		return res;
	}

	bigint operator - () { bigint res(*this); res.sign *= -1; return res; }

	bigint operator * (bigint r)
	{
		bigint res;
		res.sign = sign * r.sign;

		for (int i=0; i<len; i++) for (int j=0; j<len; j++) if (i+j<len)
			res.a[i+j] += a[i] * r.a[j];

		for (int i=0; i<len-1; i++) {
			res.a[i+1] += res.a[i] / B;
			res.a[i] %= B;
		}

		return res;
	}

	bool operator < (bigint r) { // assume both >= 0
		for (int i=len-1; i>=0; i--)
			if (a[i] != r.a[i])
				return a[i] < r.a[i];
		return false;
	}
};

struct bigdouble {
	bigint a, b;

	bigdouble(bigint a=0, bigint b=1) : a(a), b(b) {}

	bool zero() { return a.zero(); }

	bigdouble operator * (const bigdouble& r)
	{
		return bigdouble(a * r.a, b * r.b);
	}

	bigdouble operator / (const bigdouble& r)
	{
		return bigdouble(a * r.b, b * r.a);
	}

	bigdouble operator - (const bigdouble& r)
	{
		return bigdouble(a * r.b - b * r.a, b * r.b);
	}
};


double s;
bool zero(double v)
{
	double eps = 1e-4;
	return -eps <= v && v <= eps;
}

int rk(bigdouble m[][3])
{
	int n = 3;
	int r = 0;

	for (int i=0; i<n; i++) {
		bool f = false;
		for (int j=r; j<n; j++) {
			if (!m[j][r].zero()) {
				f = true;
				for (int k=0; k<n; k++)
					swap(m[j][k], m[r][k]);
				break;
			}
		}

		if (f) {
			for (int j=r+1; j<n; j++) {
				bigdouble mul = m[j][i] / m[r][i];
				for (int k=0; k<n; k++)
					m[j][k] = m[j][k] - mul * m[r][k];
			}
			r++;
		}
	}

	return r;
}

int rk(bigdouble m11, bigdouble m12, bigdouble m13, bigdouble m22, bigdouble m23, bigdouble m33)
{
	bigdouble m21 = m12;
	bigdouble m31 = m13;
	bigdouble m32 = m23;

	bigdouble m[3][3] = {m11, m12, m13, m21, m22, m23, m31, m32, m33};

	return rk(m);
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i=0; i<n; i++) for (int j=0; j<m; j++) scanf("%lld", &a[i][j]);
	scanf("%d%d", &r, &c);
	for (int i=0; i<r; i++) for (int j=0; j<c; j++) scanf("%lld", &b[i][j]);

	int ans = 0;
	for (int i=0; i<=n-r; i++) {
		for (int j=0; j<=m-c; j++) {
			bigint ass, abs, bss, as, bs, os;
			for (int k=0; k<r; k++) {
				for (int l=0; l<c; l++) {
					ass = ass + a[i+k][j+l] * a[i+k][j+l];
					abs = abs + a[i+k][j+l] * b[k][l];
					bss = bss + b[k][l] * b[k][l];
					as = as + a[i+k][j+l];
					bs = bs + b[k][l];
					os = os + bigint(1);
				}
			}

			if (rk(ass, as, -abs, os, -bs, bss) <= 2)
				ans++;
		}
	}

	printf("%d\n", ans);

	return 0;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 68