QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100891#1811. How to Move the Beansckiseki#WA 13ms6096kbC++202.3kb2023-04-28 16:27:532023-04-28 16:27:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-28 16:27:55]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:6096kb
  • [2023-04-28 16:27:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1025;
int dp[maxn][maxn];

using monoid = array<int,4>;

const monoid ID = {0, 1, 2, 3};

int mex(vector<int> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i < (int)v.size(); i++)
        if (v[i] != i)
            return i;
    return (int)v.size();
}

monoid f(monoid lhs, monoid rhs) {
    monoid res;
    for (int j = 0; j < 4; j++)
        res[j] = rhs[lhs[j]];
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<string> s(N);
    for (int i = 0; i < N; i++) {
        cin >> s[i];
    }

    for (int j = 0; j < M; j++)
        dp[N][j] = 1e9;

    for (int i = N - 1; i >= 0; i--) {
        vector<monoid> a(M);

        for (int j = 0; j < M; j++) {
            if (s[i][j] == '#') {
                a[j] = {3, 3, 3, 3};
            } else {
                for (int t = 0; t < 4; t++) {
                    a[j][t] = mex({ t, dp[i + 1][j] });
                }
            }
        }

        vector<int> rig(M), lef(M);

        vector<monoid> pre(M + 1), suf(M + 1);
        {
            // go right
            pre[0] = ID;
            for (int j = 0; j < M; j++) {
                pre[j + 1] = f(pre[j], a[j]);
            }

            suf[M] = ID;
            for (int j = M - 1; j >= 0; j--) {
                suf[j] = f(a[j], suf[j + 1]);
            }

            for (int j = 0; j < M; j++) {
                rig[j] = f(suf[j + 1], pre[j])[3];
            }
        }

        {
            // go left
            pre[0] = ID;
            for (int j = 0; j < M; j++) {
                pre[j + 1] = f(a[j], pre[j]);
            }

            suf[M] = ID;
            for (int j = M - 1; j >= 0; j--) {
                suf[j] = f(suf[j + 1], a[j]);
            }

            for (int j = 0; j < M; j++) {
                lef[j] = f(pre[j], suf[j + 1])[3];
            }
        }


        for (int j = 0; j < M; j++) {
            dp[i][j] = mex({ rig[j], lef[j], dp[i + 1][j] });
        }
    }

    int ans = 0;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (s[i][j] == 'B')
                ans ^= dp[i][j];

    cout << (ans == 0 ? "Bob\n" : "Alice\n");

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3308kb

input:

2 3
B.#
#..

output:

Alice

result:

ok "Alice"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3400kb

input:

1 1
B

output:

Bob

result:

ok "Bob"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3400kb

input:

1 3
B#.

output:

Alice

result:

ok "Alice"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

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

output:

Bob

result:

ok "Bob"

Test #5:

score: 0
Accepted
time: 13ms
memory: 4560kb

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: 2ms
memory: 3588kb

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: 2ms
memory: 3560kb

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: 1ms
memory: 3536kb

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: 0
Accepted
time: 11ms
memory: 4460kb

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:

Bob

result:

ok "Bob"

Test #10:

score: -100
Wrong Answer
time: 7ms
memory: 6096kb

input:

288 94
B....BB....BB.BBB.BBBB..B.B.B.....BBBB.B..BBBBBB.B..BBBBBBB....BBB.BBBBB.B.BBBB..B..B.B.BBB..B
BB#.#B#BBB.B#BB..BBB.B#BB#B#BB#BBBBBB####.B.B...BBB.BB.B.#.B.B.B.#.B.B.#.#..B..BB..B#..B.#....
BBBBBBB...B.BB.B..BB..BBBB.BBBBB.BBBB..BBBBBB.BB....B.BBBB.BB.BBB..B.BBBB.B.BBBBBB..BBB.BBB.B.
.B....B....

output:

Bob

result:

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