QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234767 | #1811. How to Move the Beans | sinsop90 | WA | 7ms | 41496kb | C++14 | 2.5kb | 2023-11-01 22:01:40 | 2023-11-01 22:01:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int n, m, Lt[maxn][5], Rt[maxn][5], Lf[maxn][5], Rf[maxn][5], f[maxn][maxn], L[maxn], R[maxn];
char s[maxn][maxn];
int mex(int a = -1, int b = -1, int c = -1) {
int res = 0;
if(a == 0 || b == 0 || c == 0) res ++;
if(a == 1 || b == 1 || c == 1) res ++;
if(a == 2 || b == 2 || c == 2) res ++;
return res;
}
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> s[i];
memset(Lt, -1, sizeof(Lt)), memset(Lf, -1, sizeof(Lf)), memset(Rt, -1, sizeof(Rt)), memset(Rf, -1, sizeof(Rf)), memset(f, -1, sizeof(f));
// cout << Lf
for(int i = n;i >= 1;i--) {
// cout << i << '\n';
int pos = -1;
for(int j = 0;j < m;j++) if(s[i][j] == '#') pos = j;
if(pos == -1) {
for(int j = 0;j <= 3;j++) Lt[0][j] = Lf[m - 1][j] = Rt[m - 1][j] = Rf[0][j] = j;
for(int j = 1;j < m;j++) for(int k = 0;k <= 3;k++) Lt[j][k] = mex(Lt[j - 1][k], f[i + 1][j]);
for(int j = m - 2;j >= 0;j--) for(int k = 0;k <= 3;k++) Rt[j][k] = mex(Rt[j + 1][k], f[i + 1][j]);
for(int j = m - 2;j >= 0;j--) for(int k = 0;k <= 3;k++) Lf[j][k] = Lt[j + 1][mex(f[i + 1][j + 1], k)];
for(int j = 1;j < m;j++) for(int k = 0;k <= 3;k++) Rf[j][k] = Rf[j - 1][mex(f[i + 1][j - 1], k)];
f[i][0] = mex(f[i + 1][0], Lf[1][mex(f[i + 1][1])], Rt[1][mex(f[i + 1][m - 1])]);
if(m >= 2) f[i][m - 1] = mex(f[i + 1][m - 1], Lt[m - 2][mex(f[i + 1][0])], Rf[m - 2][mex(f[i + 1][m - 2])]);
// cout << f[i + 1][m - 1] << " " << Lf[1][mex(f[i + 1][1])] << " " << " " << Rt[1][mex(f[i + 1][m - 1])];
for(int j = 1;j < m - 1;j++) {
f[i][j] = mex(f[i + 1][j], Lt[j - 1][mex(Lf[j + 1][mex(f[i + 1][j + 1])], f[i + 1][0])], Rt[j + 1][mex(Rf[j - 1][mex(f[i + 1][j - 1])], f[i + 1][m - 1])]);
}
}
else {
// cout<< pos << "\n";
for(int j = pos, t = 1;t <= m;j = (j + 1) % m, t ++) {
if(s[i][j] == '#') L[j] = -1;
else L[j] = mex(L[(j - 1 + m) % m], f[i + 1][j]);
// cout << L[j] << '\n';
}
for(int j = pos, t = 1;t <= m;j = (j - 1 + m) % m, t ++) {
// cout << j << " " << pos << '\n';
if(s[i][j] == '#') R[j] = -1;
else R[j] = mex(R[(j - 1 + m) % m], f[i + 1][j]);
}
for(int j = 0;j < m;j++) {
if(s[i][j] == '#') f[i][j] = -1;
else f[i][j] = mex(f[i + 1][j], L[(j - 1 + m) % m], R[(j + 1) % m]);
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++) {
for(int j = 0;j < m;j++) {
if(s[i][j] == 'B') ans ^= f[i][j];
}
}
if(ans) cout << "Alice\n";
else cout << "Bob\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 39324kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 0ms
memory: 40472kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 0ms
memory: 41152kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 3ms
memory: 40696kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: -100
Wrong Answer
time: 7ms
memory: 41496kb
input:
293 249 #B..B..BBB..B.B.B...#BBB..B#B.BBB.#B##B.BB.B.##B#B.BB..B.#B#BB.BB##B#BB#...B..BB..B.B##B.B#B.#.##..B.#..BBBB#.BB..#.BBB#B##BB....B.##B..#...B#..B.BB#B.#...B#.BB.#B#.B...BBB.B.B..B....##.B..B##.BB#B.B.BBB.B#B..#.B.B#.B##..B#.##BB.#BB#.BB.#.B..BB.BB.B BB.B.#.B#BB.B.B..B.###.B...BB.##.B...B#BB....
output:
Bob
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'