QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#355216#5107. Mosaic Browsingucup-team052#RE 92ms25600kbC++233.2kb2024-03-16 14:33:132024-03-16 14:33:13

Judging History

This is the latest submission verdict.

  • [2024-03-16 14:33:13]
  • Judged
  • Verdict: RE
  • Time: 92ms
  • Memory: 25600kb
  • [2024-03-16 14:33:13]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int md = 998244353;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) {
	return 1ull * x * y % md;
}

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

namespace Poly {
	vector <int> roots, rev;
	
	void getRevRoot(int base) {
		int n = 1 << base;
		if ((int)roots.size() == n) return;
		roots.resize(n); rev.resize(n);
		for (int i = 1; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
		for (int mid = 1; mid < n; mid <<= 1) {
			int wn = fpow(3, (md - 1) / (mid << 1));
			roots[mid] = 1;
			for (int i = 1; i < mid; i++) roots[mid + i] = mul(roots[mid + i - 1], wn);
		}
	}
	
	void ntt(vector <int> &a, int base) {
		int n = 1 << base;
		for (int i = 0; i < n; i++) {
			if (rev[i] > i) {
				swap(a[i], a[rev[i]]);
			}
		}
		for (int mid = 1; mid < n; mid <<= 1) {
			for (int i = 0; i < n; i += (mid << 1)) {
				for (int j = 0; j < mid; j++) {
					int x = a[i + j], y = mul(roots[mid + j], a[i + j + mid]);
					a[i + j] = add(x, y); a[i + j + mid] = sub(x, y);
				}
			}
		}
	}
	
	vector <int> operator * (vector <int> a, vector <int> b) {
		int n = (int)a.size() + (int)b.size() - 1, base = 0;
		while ((1 << base) < n) ++base;
		a.resize(1 << base); b.resize(1 << base);
		getRevRoot(base); ntt(a, base); ntt(b, base);
		for (int i = 0; i < (1 << base); i++) a[i] = mul(a[i], b[i]);
		ntt(a, base); reverse(a.begin() + 1, a.end());
		int inv = fpow(1 << base, md - 2);
		for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
		a.resize(n);
		return a;
	}
}

using Poly::operator *;

const int N = 1005, T = 2;

int a[N][N], b[N][N], ans[N][N], w[N], iw[N];
vector <int> f, g, h;
int n1, m1, n2, m2, cnt;

mt19937 rng(123);

int main() {
	scanf("%d%d", &n1, &m1);
	for (int i = 0; i < n1; i++) {
		for (int j = 0; j < m1; j++) {
			scanf("%d", &a[i][j]);
			if (a[i][j]) ++cnt;
		}
	}
	scanf("%d%d", &n2, &m2);
	for (int i = 0; i < n2; i++) {
		for (int j = 0; j < m2; j++) {
			scanf("%d", &b[i][j]);
		}
	}
	g.resize(n2 * m2);
	for (int _ = 1; _ <= T; _++) {
		f.clear(); f.resize(n1 * m2);
		for (int i = 1; i <= 100; i++) {
			w[i] = rng() % (md - 1) + 1;
			iw[i] = fpow(w[i], md - 2);
		}
		for (int i = 0; i < n1; i++) {
			for (int j = 0; j < m1; j++) {
				f[i * m2 + j] = w[a[i][j]];
			}
		}
		for (int i = 0; i < n2; i++) {
			for (int j = 0; j < m2; j++) {
				g[i * m2 + j] = iw[b[i][j]];
			}
		}
		reverse(f.begin(), f.end());
		h = f * g;
		for (int i = 0; i <= n2 - n1; i++) {
			for (int j = 0; j <= m2 - m1; j++) {
				if (h[i * m2 + j + (int)f.size() - 1] == cnt) {
					++ans[i][j];
				}
			}
		}
	}
	vector <pii> res;
	for (int i = 0; i <= n2 - n1; i++) {
		for (int j = 0; j <= m2 - m1; j++) {
			if (ans[i][j] == T) {
				res.emplace_back(i, j);
			}
		}
	}
	printf("%d\n", (int)res.size());
	for (auto i : res) printf("%d %d\n", i.first + 1, i.second + 1);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 85ms
memory: 23516kb

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: 92ms
memory: 25600kb

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: 80ms
memory: 25488kb

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: 0ms
memory: 8224kb

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: 0
Accepted
time: 1ms
memory: 7872kb

input:

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

output:

3
1 3
1 4
2 3

result:

ok 4 lines

Test #6:

score: 0
Accepted
time: 1ms
memory: 8216kb

input:

1 1
1
4 1
1
4
2
6

output:

1
1 1

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 8216kb

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 #8:

score: 0
Accepted
time: 0ms
memory: 7920kb

input:

2 2
1 3
0 0
1 3
1 2 3

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 8204kb

input:

1 4
4 4 4 1
1 1
2

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 7940kb

input:

1 1
0
6 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

output:

24
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4

result:

ok 25 lines

Test #11:

score: 0
Accepted
time: 0ms
memory: 7920kb

input:

1 1
2
1 5
3 2 3 3 2

output:

2
1 2
1 5

result:

ok 3 lines

Test #12:

score: 0
Accepted
time: 1ms
memory: 8212kb

input:

1 1
3
2 8
7 2 6 3 7 2 5 3
1 5 3 4 1 3 3 6

output:

5
1 4
1 8
2 3
2 6
2 7

result:

ok 6 lines

Test #13:

score: 0
Accepted
time: 1ms
memory: 7952kb

input:

2 3
1 1 0
1 1 0
1 7
1 1 1 1 1 1 1

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 1ms
memory: 7924kb

input:

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

output:

1
4 2

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 7860kb

input:

1 1
2
4 3
5 6 5
3 2 4
1 2 4
7 3 5

output:

2
2 2
3 2

result:

ok 3 lines

Test #16:

score: -100
Runtime Error

input:

5 4
1 0 1 1
0 0 1 0
1 0 0 1
1 0 0 0
0 0 1 1
3 1
1
1
1

output:


result: