QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#472806#5107. Mosaic BrowsingkarunaWA 1853ms202900kbC++204.7kb2024-07-11 19:27:402024-07-11 19:27:40

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 19:27:40]
  • 评测
  • 测评结果:WA
  • 用时:1853ms
  • 内存:202900kb
  • [2024-07-11 19:27:40]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
typedef long double ld;
#define double ld
typedef std::complex<double> cpx;
const int INF = (int)1e9 + 7;

using namespace std;

template <typename T>
vector<T> operator+ (const vector<T> &x, const vector<T> &y)
{
	int n = x.size();
	vector<T> ret(n);
	for(int i = 0; i < n; ++i) ret[i] = x[i] + y[i];
	return ret;
}
template <typename T>
vector<T> operator- (const vector<T> &x, const vector<T> &y)
{
	int n = x.size();
	vector<T> ret(n);
	for(int i = 0; i < n; ++i) ret[i] = x[i] - y[i];
	return ret;
}
template <typename T1, typename T2>
vector<T1> operator* (const vector<T1> &x, T2 y)
{
	int n = x.size();
	vector<T1> ret(n);
	for(int i = 0; i < n; ++i) ret[i] = x[i] * y;
	return ret;
}
vector<cpx> conj(vector<cpx> V)
{
	for(auto &i : V) i = conj(i);
	return V;
}

const double pi = acos(-1);
int M, B;
vector<int> rev;
vector<cpx> w;

void init(int _B)
{
	B = _B;
	M = 1 << B;
	w.resize(M);
	rev.resize(M);
	for(int i = 0; i < M; ++i)
	{
		w[i] = { cos(pi * i / M), sin(pi * i / M) };
		rev[i] = (rev[i / 2] >> 1) | ((i & 1) << (B - 1));
	}
}

template <typename T>
void dft(vector<T> &F, bool inv)
{
	int n = F.size();
	int b = __lg(n);
	for(int i = 0; i < n; ++i)
	{
		int p = rev[i] >> (B - b);
		if(i < p) swap(F[i], F[p]);
	}
	for(int d = 1; d < n; d *= 2)
	{
		for(int i = 0; i < n; i += 2 * d)
		{
			for(int j = 0; j < d; ++j)
			{
				T a = F[i + j];
				T b = F[i + j + d] * (inv ? conj(w[M / d * j]) : w[M / d * j]);
				F[i + j] = a + b;
				F[i + j + d] = a - b;
			}
		}
	}
	if(inv) for(int i = 0; i < n; ++i) F[i] = F[i] * (double(1) / n);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int a, b; cin >> a >> b;
	int A[a][b];
	for(auto &i : A) for(auto &j : i) cin >> j;
	int c, d; cin >> c >> d;
	int B[c][d];
	for(auto &i : B) for(auto &j : i) cin >> j;

	int n = 1, m = 1;
	while(n < a + c) n <<= 1;
	while(m < b + d) m <<= 1;
	init(15);

	vector<vector<cpx>> X(n, vector<cpx>(m));
	vector<vector<cpx>> Y(n, vector<cpx>(m));
	vector<vector<cpx>> Z(n, vector<cpx>(m));
	vector<vector<cpx>> WX(n, vector<cpx>(m));
	vector<vector<cpx>> WY(n, vector<cpx>(m));
	vector<vector<cpx>> WZ(n, vector<cpx>(m));
	for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) X[i][j].real(A[a - i - 1][b - j - 1] * A[a - i - 1][b - j - 1] * A[a - i - 1][b - j - 1]);
	for(int i = 0; i < c; ++i) for(int j = 0; j < d; ++j) X[i][j].imag(B[i][j]);
	for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) Y[i][j].real(A[a - i - 1][b - j - 1] * A[a - i - 1][b - j - 1]);
	for(int i = 0; i < c; ++i) for(int j = 0; j < d; ++j) Y[i][j].imag(B[i][j] * B[i][j]);
	for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) Z[i][j].real(A[a - i - 1][b - j - 1]);
	for(int i = 0; i < c; ++i) for(int j = 0; j < d; ++j) Z[i][j].imag(B[i][j] * B[i][j] * B[i][j]);
	
	dft(X, false); for(auto &i : X) dft(i, false);
	dft(Y, false); for(auto &i : Y) dft(i, false);
	dft(Z, false); for(auto &i : Z) dft(i, false);

	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
	{
		int _i = (n - i) % n;
		int _j = (m - j) % m;
		cpx p = (X[i][j] + conj(X[_i][_j])) * cpx(0.5, 0);
		cpx q = (X[i][j] - conj(X[_i][_j])) * cpx(0, -0.5);
		WX[i][j] = p * q;
	}
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
	{
		int _i = (n - i) % n;
		int _j = (m - j) % m;
		cpx p = (Y[i][j] + conj(Y[_i][_j])) * cpx(0.5, 0);
		cpx q = (Y[i][j] - conj(Y[_i][_j])) * cpx(0, -0.5);
		WY[i][j] = cpx(-2.0, 0) * p * q;
	}
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
	{
		int _i = (n - i) % n;
		int _j = (m - j) % m;
		cpx p = (Z[i][j] + conj(Z[_i][_j])) * cpx(0.5, 0);
		cpx q = (Z[i][j] - conj(Z[_i][_j])) * cpx(0, -0.5);
		WZ[i][j] = p * q;
	}

	dft(WX, true); for(auto &i : WX) dft(i, true);
	dft(WY, true); for(auto &i : WY) dft(i, true);
	dft(WZ, true); for(auto &i : WZ) dft(i, true);

	vector<pii> ans;
	for(int i = 0; i < c - a + 1; ++i) for(int j = 0; j < d - b + 1; ++j)
	{
		if((ll)round(WX[i + a - 1][j + b - 1].real())
		 + (ll)round(WY[i + a - 1][j + b - 1].real())
		 + (ll)round(WZ[i + a - 1][j + b - 1].real()) <= 10) ans.push_back({i, j});
	}

	// for(int i = 0; i < n; ++i)
	// {
	// 	for(int j = 0; j < m; ++j)
	// 	{
	// 		cout << (ll)round(W[i][j].real()) << ' ';
	// 	}
	// 	cout << endl;
	// }

	cout << ans.size() << '\n';
	for(auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1853ms
memory: 202648kb

input:

100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

2005
1 1
1 101
1 201
1 301
1 401
2 1
2 101
2 201
2 301
2 401
3 1
3 101
3 201
3 301
3 401
4 1
4 101
4 201
4 301
4 401
5 1
5 101
5 201
5 301
5 401
6 1
6 101
6 201
6 301
6 401
7 1
7 101
7 201
7 301
7 401
8 1
8 101
8 201
8 301
8 401
9 1
9 101
9 201
9 301
9 401
10 1
10 101
10 201
10 301
10 401
11 1
11 10...

result:

ok 2006 lines

Test #2:

score: 0
Accepted
time: 1823ms
memory: 202748kb

input:

250 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

1255
1 1
1 101
1 201
1 301
1 401
2 1
2 101
2 201
2 301
2 401
3 1
3 101
3 201
3 301
3 401
4 1
4 101
4 201
4 301
4 401
5 1
5 101
5 201
5 301
5 401
6 1
6 101
6 201
6 301
6 401
7 1
7 101
7 201
7 301
7 401
8 1
8 101
8 201
8 301
8 401
9 1
9 101
9 201
9 301
9 401
10 1
10 101
10 201
10 301
10 401
11 1
11 10...

result:

ok 1256 lines

Test #3:

score: 0
Accepted
time: 1835ms
memory: 202900kb

input:

500 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

5
1 1
1 101
1 201
1 301
1 401

result:

ok 6 lines

Test #4:

score: 0
Accepted
time: 3ms
memory: 4344kb

input:

1 1
1
3 3
1 1 1
1 1 1
1 1 1

output:

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

result:

ok 10 lines

Test #5:

score: -100
Wrong Answer
time: 5ms
memory: 4400kb

input:

1 1
2
2 4
1 1 2 2
1 3 2 3

output:

8
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4

result:

wrong answer 1st lines differ - expected: '3', found: '8'