QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19830 | #1811. How to Move the Beans | conqueror_of_zky# | WA | 3ms | 3860kb | C++14 | 2.8kb | 2022-02-11 18:13:13 | 2022-05-06 07:14:52 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;
inline int read() {
int x = 0, f = 1; char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = 0;
for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
return f ? x : -x;
}
const int maxn = 1000;
int n, m, f[maxn + 5][2], g[maxn + 5], h[maxn + 5], vis[maxn + 5][2];
char s[maxn + 5][maxn + 5];
inline int nxt(int x) {return x == m ? 1 : x + 1;}
inline int prv(int x) {return x == 1 ? m : x - 1;}
inline int mex(int a, int b) {return !a || !b ? 1 + (a == 1 || b == 1) : 0;}
struct PP {
int p[3];
inline int& operator [] (int x) {return p[x];}
friend PP operator + (PP a, PP b) {
PP c;
rep(i, 0, 2) c[i] = b[a[i]];
return c;
}
void debug() {cout << p[0] << ' ' << p[1] << ' ' << p[2] << '\n';}
}mt[maxn + 5], pre[maxn + 5][2], suf[maxn + 5][2], null;
int main() {
//freopen("in.txt", "r", stdin);
rep(i, 0, 2) null[i] = i;
n = read(), m = read();
rep(i, 1, n) cin >> s[i] + 1;
int ans = 0;
rep(i, 1, m) h[i] = 2;
per(i, n, 1) {
rep(j, 1, m) g[j] = h[j];
if(count(s[i] + 1, s[i] + m + 1, '#') == 0) {
if(m == 1) {
h[1] = s[i][1] == '#' ? 2 : g[1];
continue;
}
rep(j, 1, m) {
rep(c, 0, 2) mt[j][c] = mex(c, g[j]);
}
pre[0][0] = pre[0][1] = suf[m + 1][0] = suf[m + 1][1] = null;
rep(j, 1, m) {
pre[j][0] = pre[j - 1][0] + mt[j];
pre[j][1] = mt[j] + pre[j - 1][1];
}
per(j, m, 1) {
suf[j][0] = suf[j + 1][0] + mt[j];
suf[j][1] = mt[j] + suf[j + 1][1];
}
rep(j, 1, m) {
h[j] = mex((suf[j + 1][1] + pre[j - 1][0])[2], (pre[j - 1][1] + suf[j + 1][0])[2]);
}
}
else {
rep(j, 1, m) vis[j][0] = vis[j][1] = 0;
function<int(int)> opt[2] = {prv, nxt};
function<int(int, int)> dfs = [&] (int u, int flg) {
if(s[i][u] == '#') return 2;
if(vis[u][flg]) return f[u][flg];
vis[u][flg] = 1;
f[u][flg] = mex(dfs(opt[flg](u), flg), g[u]);
return f[u][flg];
};
rep(j, 1, m) {
h[j] = (s[i][j] == '#' ? 2 : mex(dfs(prv(j), 0), dfs(nxt(j), 1)));
}
}
rep(j, 1, m) if(s[i][j] == 'B') ans ^= h[j];
//rep(j, 1, m) cout << h[j] << " \n"[j == m];
}
puts(ans ? "Alice" : "Bob");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 3ms
memory: 3568kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 3ms
memory: 3672kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: -100
Wrong Answer
time: 3ms
memory: 3860kb
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'