QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #132629 | #6377. LaLa and Magic Stone | UrgantTeam | WA | 21ms | 8496kb | C++23 | 5.0kb | 2023-07-30 20:27:48 | 2023-07-30 20:27:50 |
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},
{3, 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 && b[i + 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) || (i + 3 <= n && j + 2 <= m && b[i + 3][j + 2] && b[i + 3][j + 1] && !b[i][j + 3] && !b[i][j + 4] && i + 2 <= n && j + 3 <= m && !b[i + 2][j + 3])) {
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: 1ms
memory: 5536kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5520kb
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: 5632kb
input:
3 4 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
3 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 3 111 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
4 4 1111 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
4 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 8496kb
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: 8388kb
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: 7ms
memory: 8444kb
input:
1000 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
3 3 000 010 010
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 5524kb
input:
3 3 000 011 000
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
3 3 010 010 000
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
3 3 000 110 000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
4 4 1000 0000 0000 0001
output:
2
result:
ok 1 number(s): "2"
Test #17:
score: 0
Accepted
time: 1ms
memory: 5644kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #18:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
3 3 010 101 101
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
3 4 1011 0100 1111
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
3 1000 10011010111111111111000101011100101000000011110011011000110000100110110110111110000111011001010010011100001111111011111111110010110100011101011100100100001110010011111011111101001110011010010110110011001100101010001101100111101001001001101000101011101000100100001111100000010010111101101001000...
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
4 3 010 101 110 000
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
4 4 0110 1010 1101 1110
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
4 1000 01001110100001111110010111111001110111001110100100101101001110110111001111101100111110001110100000010101110001100001011000100111001111101110100001010101100011101110000010110101101100001000111101111000110100110000110111111101111101000011100001001110011000110110001110110011010111101101101001000...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 0ms
memory: 8420kb
input:
1000 3 011 011 101 011 101 011 100 101 110 010 101 010 010 100 100 000 010 101 011 110 101 110 011 101 100 110 011 011 101 101 111 001 101 100 110 110 101 011 010 100 100 110 110 100 110 101 111 011 101 001 101 101 001 110 110 010 101 110 010 100 010 110 010 110 111 101 100 001 000 001 110 001 111 0...
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 0ms
memory: 8376kb
input:
1000 4 1000 0000 1010 0100 0101 0011 1101 0000 1001 0001 1111 0100 1101 0111 1110 1001 0100 0011 0011 1000 1001 1100 0110 0100 1100 0111 0010 0110 1111 1101 1001 0010 1110 1100 1000 0111 0010 0100 1001 0101 1111 0000 0110 0011 0110 1000 0110 1111 0000 0000 1011 1000 0000 0101 1001 0001 0100 0110 011...
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 21ms
memory: 8400kb
input:
1000 1000 00111010100111001111101110110011111101010111001010011001011000100100110011000111000000100010011101100011001001101110100001000101111100100110101010101011000111010101000110000110001100110011111000011100100001001110110000110010000111010110100001010100100101000011110001010111011011101111001011...
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 2ms
memory: 5772kb
input:
58 17 10001101010001111 10111101010000111 10001100010000000 00011000111000010 01110000111111010 00010000111111111 11110001111110001 11100010001100001 11100000000100001 11100000000100011 11110001000111000 00010001000110000 00000101000010000 00000101000010001 10001111100011111 11111111000111000 111000...
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
16 13 1111111111111 1111111111111 1000110001111 1000100000001 1000000000000 1100000010000 1111111111000 1111111111111 1110001111111 1110000111000 1110000110000 1111000110000 1100010000001 1000010000111 1000010000111 1000111000111
output:
0
result:
ok 1 number(s): "0"
Test #29:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
9 78 000111111111111111000111111111100011100010000001111111111111111111111111110001 010100011111111111000011111111100001000000000000111111110001111000110001110000 110100001111110001000011100011100001000000000000010111110000110000100001110000 1000000011111100001000111000011100010001000110000100001100...
output:
0
result:
ok 1 number(s): "0"
Test #30:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
18 55 1111110001111111111111000111111111111111111000111111111 1111110000100010001000000011100011000111110000111111111 1110000000111010000010000011100001000000010000111111111 1100001000100010000010100011100001000000000001100011111 1100001110001111000111111111110001100000001111100000101 11000111100001...
output:
0
result:
ok 1 number(s): "0"
Test #31:
score: -100
Wrong Answer
time: 1ms
memory: 6140kb
input:
124 5 10001 10000 10000 11000 00011 00001 00001 10001 00011 00001 00001 10001 11111 00011 01011 01011 11111 11111 10001 00001 00001 00011 10001 00001 00001 00011 00011 01011 01011 11111 11111 11111 11000 10000 10000 10001 11111 11111 11111 11111 11000 10000 10000 10001 10001 10000 10000 11000 11000 ...
output:
0
result:
wrong answer 1st numbers differ - expected: '1048576', found: '0'