QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165374#7180. Forward-Capturing Pawnsucup-team004#AC ✓1070ms194000kbC++2011.2kb2023-09-05 17:46:562023-09-05 17:46:56

Judging History

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

  • [2023-09-05 17:46:56]
  • 评测
  • 测评结果:AC
  • 用时:1070ms
  • 内存:194000kb
  • [2023-09-05 17:46:56]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

int win[65][64][64][5][2] {};
int h[65][64][64][5][2] {};
int deg[65][64][64][5][2] {};
bool r[65][64][64][5][2] {};

int edges;
int to[20000000];
int nxt[20000000];

int pack(int a, int b, int c, int d, int e) {
    return (((a * 64 + b) * 64 + c) * 5 + d) * 2 + e;
}

void add(int a1, int b1, int c1, int d1, int e1,
        int a2, int b2, int c2, int d2, int e2) {
    // if (a2 == 30 && b2 == 1 && c2 == 38 && d2 == 0 && e2 == 0) {
    //     std::cerr << a1 << " " << b1 << " " << c1 << " " << d1 << " " << e1 << "\n";
    // }
    int v = pack(a2, b2, c2, d2, e2);
    deg[a2][b2][c2][d2][e2]++;
    int &H = h[a1][b1][c1][d1][e1];
    ++edges;
    to[edges] = v;
    nxt[edges] = H;
    H = edges;
}

std::array<int, 5> unpack(int s) {
    return {s / (64 * 64 * 5 * 2), s / (64 * 5 * 2) % 64, s / (5 * 2) % 64, s / 2 % 5, s % 2};
}

bool legal(int x, int y) {
    return 0 <= x && x < 8 && 0 <= y && y < 8;
}

bool contains(i64 a, int b) {
    return a >> b & 1;
}

i64 moves(int a, int t, int u, int v1, int v2) {
    i64 ans = 0;
    const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
    const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
    if (t == 0) {
        int x = a / 8, y = a % 8;
        if (legal(x, y + 1)) {
            int b = x * 8 + (y + 1);
            if (u != b) {
                ans |= 1LL << b;
                if (v1 != b && v2 != b && legal(x, y + 2) && y == 1) {
                    int c = x * 8 + (y + 2);
                    if (u != c) {
                        ans |= 1LL << c;
                    }
                }
            }
        }
    } else if (t == 1) {
        for (int k = 0; k < 8; k++) {
            int x = a / 8, y = a % 8;
            while (true) {
                x += dx[k];
                y += dy[k];
                if (!legal(x, y)) {
                    break;
                }
                int b = x * 8 + y;
                if (u == b) {
                    break;
                }
                ans |= 1LL << b;
                if (v1 == b || v2 == b) {
                    break;
                }
            }
        }
    } else if (t == 2) {
        for (int k = 0; k < 8; k += 2) {
            int x = a / 8, y = a % 8;
            while (true) {
                x += dx[k];
                y += dy[k];
                if (!legal(x, y)) {
                    break;
                }
                int b = x * 8 + y;
                if (u == b) {
                    break;
                }
                ans |= 1LL << b;
                if (v1 == b || v2 == b) {
                    break;
                }
            }
        }
    } else if (t == 3) {
        for (int k = 1; k < 8; k += 2) {
            int x = a / 8, y = a % 8;
            while (true) {
                x += dx[k];
                y += dy[k];
                if (!legal(x, y)) {
                    break;
                }
                int b = x * 8 + y;
                if (u == b) {
                    break;
                }
                ans |= 1LL << b;
                if (v1 == b || v2 == b) {
                    break;
                }
            }
        }
    } else if (t == 4) {
        const int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
        const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
        for (int k = 0; k < 8; k++) {
            int x = a / 8, y = a % 8;
            while (true) {
                x += dx[k];
                y += dy[k];
                if (!legal(x, y)) {
                    break;
                }
                int b = x * 8 + y;
                if (u == b) {
                    break;
                }
                ans |= 1LL << b;
                break;
            }
        }
    } else {
        for (int k = 0; k < 8; k++) {
            int x = a / 8, y = a % 8;
            while (true) {
                x += dx[k];
                y += dy[k];
                if (!legal(x, y)) {
                    break;
                }
                int b = x * 8 + y;
                if (u == b) {
                    break;
                }
                ans |= 1LL << b;
                break;
            }
        }
    }
    return ans;
}

int read() {
    std::string s;
    std::cin >> s;
    
    return (s[0] - 'a') * 8 + (s[1] - '1');
}

bool check(int a, int b, int c, int d, int e) {
    if (e == 0) {
        if (a < 64 && contains(moves(a, d, b, c, -1), c)) {
            return true;
        }
        if (contains(moves(b, 5, a, c, -1), c)) {
            return true;
        }
    } else {
        if (contains(moves(c, 5, -1, a, b), b)) {
            return true;
        }
    }
    return false;
}

bool reasonable(int a, int b, int c, int d, int e) {
    if (a == b || b == c || c == a) {
        return false;
    }
    if (a == 64 && d != 0) {
        return false;
    }
    if (a < 64 && d == 0 && (a % 8 == 0 || a % 8 == 7)) {
        return false;
    }
    if (check(a, b, c, d, e)) {
        return false;
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int tot = 0;
    for (int a = 0; a < 65; a++) {
        for (int b = 0; b < 64; b++) {
            for (int c = 0; c < 64; c++) {
                for (int d = 0; d < 5; d++) {
                    for (int e = 0; e < 2; e++) {
                        if (reasonable(a, b, c, d, e)) {
                            r[a][b][c][d][e] = true;
                            tot++;
                        }
                    }
                }
            }
        }
    }
    // std::cerr << tot << "\n";
    tot = 0;
    
    for (int a = 0; a < 65; a++) {
        for (int b = 0; b < 64; b++) {
            for (int c = 0; c < 64; c++) {
                for (int d = 0; d < 5; d++) {
                    for (int e = 0; e < 2; e++) {
                        if (r[a][b][c][d][e]) {
                            if (e == 0) {
                                if (a < 64) {
                                    i64 res = moves(a, d, b, c, -1);
                                    for (int v = 0; v < 64; v++) {
                                        if (contains(res, v)) {
                                            if (v % 8 != 7 || d != 0) {
                                                if (r[v][b][c][d][!e]) {
                                                    add(v, b, c, d, !e, a, b, c, d, e);
                                                    tot++;
                                                }
                                            } else {
                                                for (int t = 1; t < 5; t++) {
                                                    if (r[v][b][c][t][!e]) {
                                                        add(v, b, c, t, !e, a, b, c, d, e);
                                                        tot++;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                                i64 res = moves(b, 5, a, c, -1);
                                for (int v = 0; v < 64; v++) {
                                    if (contains(res, v) && r[a][v][c][d][!e]) {
                                        add(a, v, c, d, !e, a, b, c, d, e);
                                        tot++;
                                    }
                                }
                            } else {
                                i64 res = moves(c, 5, -1, a, b);
                                for (int v = 0; v < 64; v++) {
                                    if (contains(res, v)) {
                                        if (v == a) {
                                            if (r[64][b][v][0][!e]) {
                                                add(64, b, v, 0, !e, a, b, c, d, e);
                                                tot++;
                                            }
                                        } else {
                                            if (r[a][b][v][d][!e]) {
                                                add(a, b, v, d, !e, a, b, c, d, e);
                                                tot++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    // std::cerr << tot << "\n";
    
    std::queue<int> q;
    std::memset(win, -1, sizeof(win));
    for (int a = 0; a < 65; a++) {
        for (int b = 0; b < 64; b++) {
            for (int c = 0; c < 64; c++) {
                for (int d = 0; d < 5; d++) {
                    for (int e = 0; e < 2; e++) {
                        if (r[a][b][c][d][e] && !deg[a][b][c][d][e]) {
                            win[a][b][c][d][e] = check(a, b, c, d, !e);
                            q.push(pack(a, b, c, d, e));
                        }
                    }
                }
            }
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        auto [a, b, c, d, e] = unpack(u);
        for (int i = h[a][b][c][d][e]; i; i = nxt[i]) {
            int v = to[i];
            auto [a1, b1, c1, d1, e1] = unpack(v);
            if (win[a1][b1][c1][d1][e1] == -1) {
                if (e1 == 0 && win[a][b][c][d][e] == 1) {
                    win[a1][b1][c1][d1][e1] = 1;
                    q.push(v);
                } else if (e1 == 0 && --deg[a1][b1][c1][d1][e1] == 0) {
                    win[a1][b1][c1][d1][e1] = 0;
                    q.push(v);
                } else if (e1 == 1 && win[a][b][c][d][e] == 0) {
                    win[a1][b1][c1][d1][e1] = 0;
                    q.push(v);
                } else if (e1 == 1 && --deg[a1][b1][c1][d1][e1] == 0) {
                    win[a1][b1][c1][d1][e1] = 1;
                    q.push(v);
                }
            }
        }
    }
    
    int t;
    std::cin >> t;
    
    for (int _ = 0; _ < t; _++) {
        int b = read();
        int a = read();
        int c = read();
        int d = 0;
        std::string s;
        std::cin >> s;
        int e = s == "w" ? 0 : 1;
        // std::cerr << a << " " << b << " " << c << " " << d << " " << e << "\n";
        std::cout << (win[a][b][c][d][e] == 1 ? "Win" : "Draw") << "\n";
    }
    // std::cerr << win[30][1][38][1][1] << "\n";
    // std::cerr << win[31][1][38][1][1] << "\n";
    // std::cerr << win[31][1][38][2][1] << "\n";
    // std::cerr << win[31][1][38][3][1] << "\n";
    // std::cerr << win[31][1][38][4][1] << "\n";
    // std::cerr << win[30][0][38][0][1] << "\n";
    // std::cerr << win[30][2][38][0][1] << "\n";
    // std::cerr << win[30][8][38][0][1] << "\n";
    // std::cerr << win[30][9][38][0][1] << "\n";
    // std::cerr << win[30][1][38][0][1] << "\n";
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 973ms
memory: 189852kb

input:

6
a2 d7 e7 w
b6 d7 e7 b
b6 d7 e7 w
b5 a2 b2 w
a6 a2 a4 b
g6 g7 h8 b

output:

Draw
Draw
Win
Win
Draw
Draw

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 1070ms
memory: 194000kb

input:

332912
h8 h7 f8 b
h8 h7 f8 w
h8 h7 e8 b
h8 h7 e8 w
h8 h7 d8 b
h8 h7 d8 w
h8 h7 c8 b
h8 h7 c8 w
h8 h7 b8 b
h8 h7 b8 w
h8 h7 a8 b
h8 h7 a8 w
h8 h7 f7 b
h8 h7 f7 w
h8 h7 e7 b
h8 h7 e7 w
h8 h7 d7 b
h8 h7 d7 w
h8 h7 c7 b
h8 h7 c7 w
h8 h7 b7 b
h8 h7 b7 w
h8 h7 a7 b
h8 h7 a7 w
h8 h7 h6 b
h8 h7 h6 w
h8 h7 g...

output:

Draw
Draw
Draw
Win
Win
Win
Win
Win
Win
Win
Win
Win
Draw
Draw
Draw
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Draw
Win
Draw
Win
Draw
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win
Win...

result:

ok 332912 lines

Extra Test:

score: 0
Extra Test Passed