QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#467774#5107. Mosaic BrowsingkarunaWA 5831ms104132kbC++203.5kb2024-07-08 17:25:442024-07-08 17:25:45

Judging History

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

  • [2024-07-08 17:25:45]
  • 评测
  • 测评结果:WA
  • 用时:5831ms
  • 内存:104132kb
  • [2024-07-08 17:25:44]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef long double ld;
namespace fft {
	typedef complex<ld> cpx;

	const ld pi = acos(-1);
	const int D = 1000;

	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));
		}
	}
	void dft(vector<cpx> &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++) {
					cpx r = w[M / d * j];
					if (inv) r = conj(r);
					cpx a = F[i + j];
					cpx b = F[i + j + d] * r;
					F[i + j] = a + b;
					F[i + j + d] = a - b;
				}
			}
		}
		if (inv) for (int i = 0; i < n; i++) F[i] /= n;
	}
	void dft_2d(vector<vector<cpx>> &F, bool rev) {
		int n = F.size();
		int m = F[0].size();
		for (int i = 0; i < n; i++) dft(F[i], rev);
		for (int i = 0; i < m; i++) {
			vector<cpx> G(n);
			for (int j = 0; j < n; j++) G[j] = F[j][i];
			dft(G, rev);
			for (int j = 0; j < n; j++) F[j][i] = G[j];
		}
	}
	vector<vector<ll>> multiply(vector<vector<ll>> F, vector<vector<ll>> G) {
		int n = 1, m = 1;
		while (n < F.size() + G.size()) n *= 2;
		while (m < F[0].size() + G[0].size()) m *= 2;

		vector<vector<cpx>> P(n), Q(n);
		for (int i = 0; i < n; i++) {
			P[i].resize(m);
			Q[i].resize(m);
		}
		for (int i = 0; i < F.size(); i++) for (int j = 0; j < F[0].size(); j++) {
			P[i][j] = {(ld)F[i][j], (ld)0};
		}
		for (int i = 0; i < G.size(); i++) for (int j = 0; j < G[0].size(); j++) {
			Q[i][j] = {(ld)G[i][j], (ld)0};
		}

		dft_2d(P, false);
		dft_2d(Q, false);
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) P[i][j] *= Q[i][j];

		dft_2d(P, true);

		vector<vector<ll>> R(n);
		for (int i = 0; i < n; i++) {
			R[i].resize(m);
			for (int j = 0; j < m; j++) R[i][j] = (ll)round(P[i][j].real());
		}
		return R;
	}
}
vector<vector<ll>> F[3], G[3], R[3];

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

	int n1, m1;
	cin >> n1 >> m1;
	
	vector<vector<ll>> C(n1, vector<ll>(m1));
	for (int i = 0; i < n1; i++) for (int j = 0; j < m1; j++) cin >> C[n1 - 1 - i][m1 - 1 - j];

	int n2, m2;
	cin >> n2 >> m2;
	
	vector<vector<ll>> A(n2, vector<ll>(m2));
	for (int i = 0; i < n2; i++) for (int j = 0; j < m2; j++) cin >> A[i][j];

	F[2] = C;
	for (int t = 2; t > 0; t--) {
		F[t - 1] = F[t];
		for (int i = 0; i < n1; i++) for (int j = 0; j < m1; j++) F[t - 1][i][j] *= C[i][j];
	}

	G[0] = vector<vector<ll>>(n2, vector<ll>(m2, 1));
	for (int t = 0; t < 2; t++) {
		G[t + 1] = G[t];
		for (int i = 0; i < n2; i++) for (int j = 0; j < m2; j++) G[t + 1][i][j] *= A[i][j];
	}

	fft::init(11);

	vector<vector<ll>> R[3];
	for (int t = 0; t < 3; t++) R[t] = fft::multiply(F[t], G[t]);

	vector<pii> ans;
	for (int x = n1; x <= n2; x++) for (int y = m1; y <= m2; y++) {
		if (R[0][x][y] - 2 * R[1][x][y] + R[2][x][y] == 0) {
			ans.push_back({x - n1 + 1, y - m1 + 1});
		}
	}

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

详细

Test #1:

score: 0
Wrong Answer
time: 5831ms
memory: 104132kb

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:

1604
1 100
1 200
1 300
1 400
2 100
2 200
2 300
2 400
3 100
3 200
3 300
3 400
4 100
4 200
4 300
4 400
5 100
5 200
5 300
5 400
6 100
6 200
6 300
6 400
7 100
7 200
7 300
7 400
8 100
8 200
8 300
8 400
9 100
9 200
9 300
9 400
10 100
10 200
10 300
10 400
11 100
11 200
11 300
11 400
12 100
12 200
12 300
12...

result:

wrong answer 1st lines differ - expected: '2005', found: '1604'