QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355216 | #5107. Mosaic Browsing | ucup-team052# | RE | 92ms | 25600kb | C++23 | 3.2kb | 2024-03-16 14:33:13 | 2024-03-16 14:33:13 |
Judging History
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