QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19825#1811. How to Move the Beansconqueror_of_zky#WA 5ms3928kbC++142.7kb2022-02-11 17:25:432022-05-06 07:14:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 07:14:34]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3928kb
  • [2022-02-11 17:25:43]
  • 提交

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;
	}
}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][1])[2], (pre[j - 1][0] + suf[j + 1][0])[2]);
			}
		}
		else {
			rep(j, 1, m) vis[i][0] = vis[i][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: 0ms
memory: 3628kb

input:

2 3
B.#
#..

output:

Alice

result:

ok "Alice"

Test #2:

score: 0
Accepted
time: 3ms
memory: 3536kb

input:

1 1
B

output:

Bob

result:

ok "Bob"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

1 3
B#.

output:

Alice

result:

ok "Alice"

Test #4:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

5 18
#.#..#.#..###..###
##...#.#..#.#..#..
#....#.#..###..#..
##...#.#..#....#..
#.#..###..#....###

output:

Bob

result:

ok "Bob"

Test #5:

score: 0
Accepted
time: 3ms
memory: 3928kb

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:

Alice

result:

ok "Alice"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

75 13
BBB.B.BB.B.#B
BB.##...B##BB
..#.B....#.B.
BBB..#...B#BB
#B#.##B..BB..
#B..BBBB.B..#
#B##.BBBBB.B#
BBB.B..#B#B..
.BBB####.##BB
.B##...#.#.#.
#.BB#..B.B.B.
BB#BB.BBB..BB
B.#...#.BBBBB
..#B.BBBB..B#
BB..B..#.....
..B..BBBB.B#.
.B.B##B.#B.##
BBBB#...#..B#
B.BB..BBB#B.B
.#B#B...BB.BB
#.B...BB...B.
...

output:

Alice

result:

ok "Alice"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

35 38
#.#..B.B.#.BB#.B.B.B..##..B#B###BBB##.
.#.#.B#.#BBB..B..BB.#..BB..##B......#B
B.B#..B..B...##B#B..#.##.#..B.#..B##BB
#.B.B..#..B#.#.B#B##B.BBB..#.B...B..#.
B#.#.BBB..B.BB.B..BBBBB##B..BB#.B#.BB.
B##.B#...B.B.BB.BBB..#BBB.#..#B#.B..#B
B....B#B.#.BBB.B#BB...##B#...B..BB.BB.
..###.#.B#....#.....#...

output:

Alice

result:

ok "Alice"

Test #8:

score: 0
Accepted
time: 3ms
memory: 3620kb

input:

36 106
BB.B..B.BBBB.BB..BB..BB..BB...BB.B..B.B..BBBB.B.BB..B.B..BB..BBBB.B.B.BBBB..B.BBBBBBBBBBBBBBB.BB.B.BBB..BB
#BBB.BBB#..#.BB...###B.B#.B...B.#.BBBB.B..B..#B.#B#BB##.BB.#B..B#B...B....B#B#.#B.B.B.BB#..B#B#.#.#B###.B.
B.BBB.BBBBB.BBB....BB..B.BBBB.BBB.BBB.BBB.B.B.BBB.B...B.B.BBBBB.BBB....BB.BBB.B...

output:

Alice

result:

ok "Alice"

Test #9:

score: -100
Wrong Answer
time: 5ms
memory: 3912kb

input:

245 239
.BBB.BB.B.BBB..B.BB.BBBBBB..B.BBB.B.BBBBBBBBB..B..BB.B.B.BB..B.BB...B.BB.B.BB..BBB..BB..BB.BBB.BBB.BBBBB.BBBB.BB.BBBB...BBB.B..BBBBBBB..BB..B.B.B..BBBBB...BB..BBB...BBB.B..BB.BB.B.BB.BBB..B.B.BBBB.BBBBB.BBB.BBBB.BB...B.B.B...BBB.BBB.BBB..B
B#.#BB..#BB.BBB#..BB..#.B#.##B.BBB###..B#B...BB..#.#...

output:

Alice

result:

wrong answer 1st words differ - expected: 'Bob', found: 'Alice'