QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624189#6314. 过河卒propane20 257ms96876kbC++206.5kb2024-10-09 15:11:352024-10-09 15:11:37

Judging History

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

  • [2024-10-09 15:11:37]
  • 评测
  • 测评结果:20
  • 用时:257ms
  • 内存:96876kb
  • [2024-10-09 15:11:35]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<set>
#include<cassert>
using namespace std;
using LL = long long;

const int dx[4]{0, 0, 1, -1};
const int dy[4]{-1, 1, 0, 0};

const int maxn = 2e6 + 5;
int f[maxn], din[maxn], val[maxn];
bool bad[maxn];
char s[12][12];
int q[maxn];

int h[maxn], e[maxn * 4], ne[maxn * 4], idx;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int _, T;
    cin >> _ >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        int a = -1, b = -1, c = -1;
        for(int i = 0; i < n; i++){
            cin >> s[i];
            for(int j = 0; j < m; j++){
                if (s[i][j] == 'X') a = i * m + j;
                if (s[i][j] == 'O'){
                    if (b == -1) b = i * m + j;
                    else c = i * m + j;
                }
            }
        }

        const int B = n * m;
        
        auto get = [&](int x, int y, int z, int t){
            return x * B * B + y * B + z + t * (B * B * B);
        };

        for(int i = 0; i < 2 * B * B * B; i++){
            h[i] = -1;
            bad[i] = false;
            din[i] = 0;
            f[i] = -1;
            val[i] = 0;
        }

        auto check = [&](int i){
            auto [x, y] = div(i, m);
            return x >= 0 and x < n and y >= 0 and y < m and s[x][y] != '#';
        };

        auto s = [&](int j){
            auto [x, y] = div(j, m);
            return x + y;
        };

        int tmp = (s(a) + s(b) + s(c)) % 2;

        int hh = 0, tt = -1;
        for(int i = 0; i < n * m; i++){
            for(int j = 0; j < n * m; j++){
                for(int k = 0; k < n * m; k++){
                    bool flag = false;
                    if (!check(i) or !check(j) or !check(k)) flag = true;
                    if (i == j and j == k) flag = true;
                    if (j == k) flag = true;
                    if (flag){
                        bad[get(i, j, k, 0)] = bad[get(i, j, k, 1)] = true;
                    }
                    else{
                        if (i / m == 0){
                            bad[get(i, j, k, 1)] = true;
                        }
                    }
                    for(int t = 0; t < 2; t++){
                        int id = get(i, j, k, t);
                        if (bad[id]) continue;
                        if ((s(i) + s(j) + s(k) + tmp + t) % 2){
                            bad[id] = true;
                            continue;
                        }
                        if (i == j or i == k){
                            f[id] = 0;
                            q[++tt] = id;
                        }
                        else if (i / m == 0 and t == 0){
                            f[id] = 0;
                            q[++tt] = id;
                        }
                    }
                }
            }
        }
        for(int i = 0; i < n * m; i++){
            for(int j = 0; j < n * m; j++){
                for(int k = 0; k < n * m; k++){
                    for(int t = 0; t < 2; t++){
                        int cur = get(i, j, k, t);
                        if (bad[cur]) continue;
                        if (t == 0){
                            auto [x, y] = div(i, m);
                            for(int u = 0; u < 3; u++){
                                int nx = x + dx[u];
                                int ny = y + dy[u];
                                if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
                                int id = get(nx * m + ny, j, k, t ^ 1);
                                if (bad[id]) continue;
                                add(cur, id);
                                din[id] += 1;
                            }
                        }
                        else{
                            {
                                auto [x, y] = div(j, m);
                                for(int u = 0; u < 4; u++){
                                    int nx = x + dx[u];
                                    int ny = y + dy[u];
                                    if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
                                    int id = get(i, nx * m + ny, k, t ^ 1);
                                    if (bad[id]) continue;
                                    add(cur, id);
                                    din[id] += 1;
                                }
                            }
                            {
                                auto [x, y] = div(k, m);
                                for(int u = 0; u < 4; u++){
                                    int nx = x + dx[u];
                                    int ny = y + dy[u];
                                    if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
                                    int id = get(i, j, nx * m + ny, t ^ 1);
                                    if (bad[id]) continue;
                                    add(cur, id);
                                    din[id] += 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int id = 0; id < 2 * B * B * B; id++){
            if (bad[id]) continue;
            if (f[id] == -1 and din[id] == 0){
                f[id] = 0;
                q[++tt] = id;
            }
        }

        while(hh <= tt){
            auto head = q[hh++];
            int cur = f[head];
            for(int i = h[head]; ~i; i = ne[i]){
                int id = e[i];
                --din[id];
                if (cur == 0 and f[id] == -1){
                    f[id] = 1;
                    val[id] = val[head] + 1;
                    q[++tt] = id;
                }
                if (din[id] == 0 and f[id] == -1){
                    f[id] = 0;
                    val[id] = val[head] + 1;
                    q[++tt] = id;
                }
            }
        }

        if (f[get(a, b, c, 0)] == -1) cout << "Tie" << '\n';
        else{
            if (f[get(a, b, c, 0)] == 0) cout << "Black" << ' ' << val[get(a, b, c, 0)] << '\n';
            else cout << "Red" << ' ' << val[get(a, b, c, 0)] << '\n';
        }
    }

}

详细


Pretests


Final Tests

Test #1:

score: 0
Runtime Error

input:

1 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
4 1
O
O
#
X
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
#...

output:


result:


Test #2:

score: 0
Runtime Error

input:

2 10
10 10
.#.####..#
.##..#####
##.###X###
#....####.
.#.#######
#.#O###.##
..##.####.
..########
##########
##O#.#.###
10 10
..#.###.##
......#..#
....#O....
#..#.....#
...#.#####
.....#..#.
..#.....#O
X#....###.
#.....##..
.#..##....
10 10
.......##.
.O##...##.
..#.......
####..O...
....#...##
.....

output:


result:


Test #3:

score: 0
Runtime Error

input:

3 10
10 10
##.#######
###..###OO
##X####.##
...#######
#..###...#
##...#####
##..#.####
..##..##.#
###..#.#.#
#.###..##.
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
10 10
..........
.X........
..........
..........
..#.......
.....

output:


result:


Test #4:

score: 5
Accepted
time: 257ms
memory: 96876kb

input:

4 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
...#.##...
..####.##.
###.######
.####O#.X#
...####..#
.##O#..#.#
##.#..###.
#.#.#....#
.#.#####.#
.##.#.#.##
3 2
OO
##
#X
10 10
.##.##...#
..##..#.#O
.#O#.#...#
#.#.#..##.
...

output:

Tie
Black 0
Black 0
Black 0
Black 0
Black 0
Tie
Tie
Tie
Tie

result:

ok 10 lines

Test #5:

score: 0
Runtime Error

input:

5 10
10 10
..........
....O.....
..........
...X......
..........
..........
..........
..........
##########
.......O..
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 1
.
.
.
O
.
.
.
X
#
O
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........

output:


result:


Test #6:

score: 0
Runtime Error

input:

6 10
10 10
.....O....
..........
..........
..........
..........
.X........
..........
..........
##########
...O......
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 10
..........
.....O....
.............

output:


result:


Test #7:

score: 5
Accepted
time: 3ms
memory: 18080kb

input:

7 10
10 1
.
O
#
.
.
X
.
#
.
O
10 1
O
.
.
.
.
.
.
X
.
O
10 1
.
.
#
O
O
#
#
.
.
X
5 1
O
O
.
X
.
10 1
O
#
.
.
.
.
.
X
.
O
9 1
O
#
O
.
.
.
.
.
X
10 1
.
.
.
.
X
O
.
#
.
O
10 1
O
O
.
#
.
.
.
.
.
X
10 1
.
.
.
.
.
.
X
.
O
O
10 1
O
.
.
.
#
X
#
O
.
.

output:

Red 5
Red 7
Black 0
Black 2
Red 11
Black 10
Red 1
Red 11
Black 12
Red 1

result:

ok 10 lines

Test #8:

score: 5
Accepted
time: 0ms
memory: 18084kb

input:

8 10
10 1
.
.
#
.
X
#
.
O
#
O
10 1
.
O
O
.
X
.
.
.
.
.
10 1
O
O
.
.
.
.
.
.
.
X
5 1
.
#
O
X
O
10 1
O
#
.
.
.
.
X
.
.
O
9 1
O
#
O
.
.
.
.
X
.
10 1
#
.
.
.
X
O
.
#
.
O
10 1
O
O
#
#
.
.
.
.
.
X
10 1
#
.
.
.
.
.
X
.
O
O
10 1
.
#
O
.
#
O
.
X
#
.

output:

Red 3
Red 3
Red 9
Red 1
Red 9
Red 5
Red 1
Black 0
Red 11
Red 3

result:

ok 10 lines

Test #9:

score: 5
Accepted
time: 0ms
memory: 20084kb

input:

9 10
10 1
#
O
#
.
.
X
.
#
.
O
10 1
O
.
.
.
X
.
.
.
.
O
10 1
.
.
#
O
O
.
#
.
.
X
5 1
O
O
.
X
.
10 1
O
#
.
#
.
.
.
X
.
O
9 1
O
.
#
O
.
.
.
X
.
10 1
.
.
.
.
X
O
.
.
.
O
10 1
O
O
.
#
#
.
.
.
.
X
10 1
.
.
.
.
X
.
#
.
O
O
10 1
.
#
O
#
O
.
.
X
#
.

output:

Red 5
Red 5
Red 5
Black 2
Red 7
Red 5
Red 1
Red 9
Black 8
Red 3

result:

ok 10 lines

Test #10:

score: 0
Runtime Error

input:

10 10
10 10
.###..###.
.....O...#
.##.#.....
..##.##.X#
##......#.
#...#.....
....##...#
..#..O##.#
#..#.##...
.....##.#.
10 10
#...##..#.
#......##.
..##....#.
#.#.##..#O
.O...#.##.
.....##.X.
.###......
....#.#.#.
.......##.
###...##.#
10 10
#.#.......
..##..##..
..##.#X..O
....#.....
#..#....#.
#...

output:


result:


Test #11:

score: 0
Runtime Error

input:

11 10
10 10
...#.....#
..#.......
##.##.###.
##...#.##X
.....#...#
...#.#.O.#
..#...#...
.....#....
......#..#
#...#...O#
10 10
..###O#O#.
.#.###.##.
##..#..#..
....#X....
........##
........##
#...##....
...#..###.
........#.
..#...#.#.
10 10
######...#
O.X.O####.
#.#.#.#...
#.......#.
...##...#.
....

output:


result:


Test #12:

score: 0
Runtime Error

input:

12 10
10 10
##..##..O.
.#........
.#.......#
..........
#.........
.XO##.....
#.........
..........
..........
..........
5 6
#.####
#.####
#.OO##
#X####
######
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
..........
.........

output:


result:


Test #13:

score: 0
Runtime Error

input:

13 10
10 10
.##...#...
.#####..##
#..#..#..#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.##......#
..#..##..O
...#.##...
##..#O..##
..#...#...
###.....#X
..#.......
.##.#.#...
.#.#.#..#.
#......#.#
10 10
.........#
..........
O.........
..........
....O.....
....

output:


result:


Test #14:

score: 0
Runtime Error

input:

14 10
10 10
.......O..
..........
..........
O.........
..........
..........
..........
..........
.......X..
..........
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
....

output:


result:


Test #15:

score: 0
Runtime Error

input:

15 10
10 10
.########O
.........#
########.#
.........#
.#########
..........
#########.
..........
.#########
.......O.X
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 8
####....
...#..#.
.###..#.
...#.O#.
##.#..#.
...####.
.##...

output:


result:


Test #16:

score: 0
Runtime Error

input:

16 10
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
.#....#...
.#....#...
..####....
..........
..........
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:


result:


Test #17:

score: 0
Runtime Error

input:

17 10
10 10
##########
..........
..........
..########
..........
#########.
.O........
..........
#.........
O#X.......
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
#.......O.
..#.......
...##.##..
..........
..........
....

output:


result:


Test #18:

score: 0
Runtime Error

input:

18 10
10 10
O.........
#..#..###.
.#.##...#.
..X.......
.####.....
.##...##.#
...#..###.
...###..O#
..#..#....
.......###
10 10
...#.....O
........#.
........X.
..........
...#......
..........
.........#
.....O....
..#.......
..........
10 10
..O.#.....
#.#...#...
...#..###.
....#.....
..#..#..#.
#...

output:


result:


Test #19:

score: 0
Runtime Error

input:

19 10
10 10
.....#....
...#.#.#.#
#..#.##.#.
.##.....#.
.#..##.#.#
...#......
#.#.#.##..
##...#O##.
..#.#O....
.#...#..X.
10 10
.O....#...
.####....#
.###...#..
..........
###....##.
....#..##.
.#.#.#....
.##.O#..#.
#..#...#..
...#....X#
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:


result:


Test #20:

score: 0
Runtime Error

input:

20 10
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
###.......
......###.
.....#..O.
##........
..#...X...
.##.......
10 10
#...#.##..
.O##.....#
#.#.....#.
.#...#....
....#..#..
.###......
....O##.#.
.#.#.....#
..........
.#.#...X#.
10 10
......###.
..#.#..##.
.#.......#
.#.#..###.
..#.#..#..
#...

output:


result: