QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #132622 | #6377. LaLa and Magic Stone | UrgantTeam# | WA | 12ms | 8456kb | C++23 | 4.9kb | 2023-07-30 19:47:13 | 2023-07-30 19:48:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1005;
char a[maxn][maxn];
int b[maxn][maxn];
int mod = 998244353;
vector < pair < int, int > > two;
vector < pair < int, int > > v1 = {
{0, 0},
{0, 1},
{0, 2},
{1, 2},
{1, 0},
{1, -1},
{1, -2},
{2, -2},
{2, 0},
{2, 1},
{2, 2},
{3, 0},
{3, -1},
{3, -2}};
vector < pair < int, int > > v2 = {
{0, 0},
{0, 1},
{0, 2},
{1, 0},
{1, 2},
{1, 3},
{1, 4},
{2, 0},
{2, 1},
{2, 2},
{2, 4},
{3, 2},
{3, 3},
{3, 4}};
vector < pair < int, int > > v3 = {
{0, 0},
{0, 1},
{0, 2},
{1, 0},
{1, 2},
{2, -1},
{2, 0},
{2, 1},
{3, -1},
{3, 1},
{2, 2},
{4, -1},
{4, 0},
{4, 1}};
vector < pair < int, int > > v4 = {
{0, 0},
{0, 1},
{0, 2},
{1, 0},
{1, 2},
{2, 0},
{2, 1},
{2, 2},
{3, 1},
{3, 3},
{4, 1},
{4, 2},
{4, 3},
{2, 3}
};
vector < pair < int, int > > v5 = {
{0, 0},
{0, 1},
{0, 2},
{1, -1},
{1, 0},
{1, 1},
{1, 2},
{2, -1},
{2, 0},
{2, 1},
{2, 2},
{3, -1},
{0, 0},
{3, 1}
};
main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#endif // HOME
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, ans = 1, s = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
b[i][j] = (1^(a[i][j] - '0'));
s += b[i][j];
}
}
if (s % 7 != 0) {
cout << 0;
exit(0);
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (i == 0 && j == 3) continue;
if (i == 3 && j == 0) continue;
two.push_back({i, j});
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!b[i][j]) continue;
int s = 0;
for (auto [x, y] : two) {
s += b[i + x][j + y];
}
if (s == two.size() && !b[i][j + 3]) {
for (auto [x, y] : two) b[i + x][j + y] = 0;
ans = ans * 2 % mod;
continue;
}
if (i + 2 > n || j + 2 > m) {
ans = 0;
continue;
}
s = 0;
for (int x = i; x < i + 3; x++) {
for (int y = j; y < j + 3; y++) {
s += b[x][y];
}
}
if (s < 7) ans = 0;
else if (s == 7) {
if (!b[i + 1][j + 1] && (!b[i][j + 1] || !b[i + 1][j] || !b[i + 1][j + 2] || !b[i + 2][j + 1])) {
for (int x = i; x < i + 3; x++) for (int y = j; y < j + 3; y++) b[x][y] = 0;
}
else ans = 0;
} else if (s == 8) {
if (!b[i + 1][j + 1]) {
if (!b[i + 2][j - 1] && j > 1) {
s = 0;
for (auto [x, y] : v1) {
s += b[i + x][j + y];
}
if (s == v1.size()) {
for (auto [x, y] : v1) b[i + x][j + y] = 0;
} else ans = 0;
} else if (!b[i + 3][j + 1] && i + 3 <= n || (b[i + 3][j] && b[i + 3][j + 2] && i + 3 <= n && j + 2 <= m)) {
s = 0;
for (auto [x, y] : v2) {
s += b[i + x][j + y];
}
if (s == v2.size()) {
for (auto [x, y] : v2) b[i + x][j + y] = 0;
} else ans = 0;
} else if (!b[i + 1][j - 1] && !b[i + 3][j] && j > 1 && i + 3 <= n) {
s = 0;
for (auto [x, y] : v3) {
s += b[i + x][j + y];
}
if (s == v3.size()) for (auto [x, y] : v3) b[i + x][j + y] = 0;
else ans = 0;
} else {
s = 0;
for (auto [x, y] : v4) {
s += b[i + x][j + y];
}
if (s == v4.size()) for (auto [x, y] : v4) b[i + x][j + y] = 0;
else ans = 0;
}
} else ans = 0;
} else {
if (!b[i][j + 3] && j + 3 <= m) {
ans = 0;
} else {
s = 0;
for (auto [x, y] : v5) {
s += b[i + x][j + y];
}
if (s == v5.size()) {
ans = ans * 2 % mod;
for (auto [x, y] : v5) b[i + x][j + y] = 0;
}
else ans = 0;
}
}
}
}
cout << ans % mod << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5536kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
5 4 0001 0101 0000 1010 1000
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
3 3 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
3 4 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5592kb
input:
3 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
4 3 111 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 2ms
memory: 5588kb
input:
4 4 1111 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 2ms
memory: 5536kb
input:
4 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 8404kb
input:
1000 3 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 1...
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 2ms
memory: 8456kb
input:
1000 4 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 111...
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 12ms
memory: 8428kb
input:
1000 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
3 3 000 010 010
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5584kb
input:
3 3 000 011 000
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5524kb
input:
3 3 010 010 000
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5556kb
input:
3 3 000 110 000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: -100
Wrong Answer
time: 1ms
memory: 5564kb
input:
4 4 1000 0000 0000 0001
output:
0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'