QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234777 | #1811. How to Move the Beans | sinsop90 | WA | 0ms | 40260kb | C++14 | 3.1kb | 2023-11-01 22:14:16 | 2023-11-01 22:14:16 |
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 == 1) res ++;
if((a == 2 || b == 2 || c == 2) && res == 2) res ++;
return res;
}
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
cin >> n >> m;
// cout << mex(0, 2, 2) << '\n';
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]);
// cout << Rt[1][0] << " " << Rt[1][1] << " " << Rt[1][2] << '\n';
for(int j = m - 2;j >= 0;j--) for(int k = 0;k <= 3;k++) Lf[j][k] = Lf[j + 1][mex(f[i + 1][j + 1], k)];
// cout << Lf[2][0] << " " << Lf[2][1] << " " << Lf[2][2] << " " << mex(f[i + 1][3], 0) << '\n';
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])]);
// cout << f[i][0] << " " << Lf[1][mex(f[i + 1][1])] << " " << Rt[1][mex(f[i + 1][m - 1])] << '\n';
// cout << Lf[1][mex(f[i + 1][1])] << " " << Rt[1][mex(f[i + 1][m - 1])] << '\n';
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][m - 1] << " " << Lf[1][mex(f[i + 1][1])] << " " << Rt[1][mex(f[i + 1][m - 1])] << '\n';
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]);
}
}
}
// for(int i = 1;i <= n;i++) {
// for(int j = 0;j < m;j++) {
// cout << f[i][j] << " ";
// }
// cout << '\n';
// }
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: 0
Wrong Answer
time: 0ms
memory: 40260kb
input:
2 3 B.# #..
output:
Bob
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'