QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252694#7180. Forward-Capturing PawnsEWDEHSAMSWATERMELONWA 8ms9532kbC++175.9kb2023-11-16 03:31:522023-11-16 03:31:53

Judging History

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

  • [2023-11-16 03:31:53]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:9532kb
  • [2023-11-16 03:31:52]
  • 提交

answer

//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
//#define int long long
using pii = pair<int, int>;
#define ff first
#define ss second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template<typename T1, typename T2>
void mxr(T1 &a, const T2 &b) {
    if (b > a) {
        a = b;
    }
}

template<typename T1, typename T2>
void mnr(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
    }
}

const int FIELD = 64;

int used[FIELD][FIELD][FIELD + 1][2];
int dp[FIELD][FIELD][FIELD + 1][2];

int BAD[10][10];

constexpr const int N = 8;

pii getcord(int pos) {
    return {pos / N, pos % N};
}

int getpos(int i, int j) {
    return i * N + j;
}

bool checkpawnattack(int pawn, int cell) {
    auto [pi, pj] = getcord(pawn);
    if (pi == 1) {
        return getpos(pi + 1, pj) == cell ||
               getpos(pi + 2, pj) == cell;
    } else {
        return getpos(pi + 1, pj) == cell;
    }
}

int dist(int cell1, int cell2) {
    auto [i1, j1] = getcord(cell1);
    auto [i2, j2] = getcord(cell2);
    return max(abs(i1 - i2), abs(j1 - j2));
}
int convpos(string t) {
    return N * (t[1] - '1') + (t[0] - 'a');
}

bool checkkingattack(int king, int cell) {
    return dist(king, cell) < 2;
}

bool win(int wk, int bk, int wp, int mv) {
    if (wp / N == N - 1) {
        if (!checkkingattack(bk, wp) || checkkingattack(wk, wp)) {
            cerr << "";
            return true;
        }
        return false;
    }
    return false;
}

bool checkpos(int wk, int bk, int wp, int mv) {
    if (wp < N || wk == bk || wk == wp) {
        return false;
    }
    if (!mv) {
        if (checkkingattack(wk, bk)) {
            return false;
        }
        if (checkpawnattack(wp, bk)) {
            return false;
        }
    }
    return true;
}

int calc(int wk, int bk, int wp, int mv) {
    if (used[wk][bk][wp][mv] == 1) {
        return -1;
    }
    if (used[wk][bk][wp][mv] == 2) {
        return dp[wk][bk][wp][mv];
    }
//    if (checkDraw(WKpos, BKpos, WPpos, move)) {
//        used[WKpos][BKpos][WPpos][move] = 2;
//        dp[WKpos][BKpos][WPpos][move] = move;
//        return 0;
//    }
    used[wk][bk][wp][mv] = 1;
    if (bk == wp) {
        dp[wk][bk][wp][mv] = 1;
        used[wk][bk][wp][mv] = 2;
        return 1;
    }
    if (win(wk, bk, wp, mv)) {
        used[wk][bk][wp][mv] = 2;
        dp[wk][bk][wp][mv] = 0;
        return 0;
    }
    if (mv) {
        bool flag = false;
        auto [bi, bj] = getcord(bk);
        dp[wk][bk][wp][mv] = 0;
        for (int dx = 1; dx >= -1; --dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (!dx && !dy) {
                    continue;
                }
                int a = dx + bi;
                int b = dy + bj;
                if (min(a, b) < 0 || max(a, b) >= N) {
                    continue;
                }
                int cell = getpos(a, b);
                if (!checkkingattack(wk, cell) && !checkpawnattack(wp, cell)) {
                    flag = true;
                    if (checkpos(wk, cell, wp, 1 - mv)) {
                        int r = calc(wk, cell, wp, 1 - mv);
                        if (r == 1) {
                            dp[wk][bk][wp][mv] = 1;
                            break;
                        }
                    }
                }
            }
        }
        if (!flag) {
            dp[wk][bk][wp][mv] = 1;
            used[wk][bk][wp][mv] = 2;
            return 1;
        }
        used[wk][bk][wp][mv] = 2;
        return dp[wk][bk][wp][mv];
    } else {
        bool flag = false;
        auto [wi, wj] = getcord(wk);
        dp[wk][bk][wp][mv] = 1;
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (!dx && !dy) {
                    continue;
                }
                int cell = wk + dx * N + dy;
                int a = dx + wi;
                int b = dy + wj;
                if (min(a, b) < 0 || max(a, b) >= N) {
                    continue;
                }
                if (!checkkingattack(bk, cell)) {
                    flag = true;
                    if (checkpos(cell, bk, wp, 1 - mv)) {
                        int r = calc(cell, bk, wp, 1 - mv);
                        if (r == 0) {
                            dp[wk][bk][wp][mv] = 0;
                            break;
                        }
                    }
                }
            }
        }
        auto [pi, pj] = getcord(wp);
        if (pi + 1 < N) {
            int cell = wp + N;
            if (checkpos(wk, bk, cell, 1 - mv)) {
                int r = calc(wk, bk, cell, 1 - mv);
                if (!r) {
                    dp[wk][bk][wp][mv] = 0;
                }
            }
            if (pi == 1) {
                cell = cell + 2 * N;
                if (checkpos(wk, bk, cell, 1 - mv)) {
                    int r = calc(wk, bk, cell, 1 - mv);
                    if (!r) {
                        dp[wk][bk][wp][mv] = 0;
                    }
                }
            }
        }
        used[wk][bk][wp][mv] = 2;
        return dp[wk][bk][wp][mv];
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
#ifdef SYSTY257
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr);
#endif
    int n;
    cin >> n;
    while (n--) {
        string wk, wp, bk;
        cin >> wk >> wp >> bk;
        int wk1 = convpos(wk);
        int wp1 = convpos(wp);
        int bk1 = convpos(bk);
        string mv;
        cin >> mv;
        int mv1 = 0;
        if (mv == "b") {
            mv1 = 1;
        }
        int t = calc(wk1, bk1, wp1, mv1);
        if (t) {
            cout << "Draw\n";
        } else {
            cout << "Win\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 9532kb

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
Win
Draw

result:

wrong answer 5th lines differ - expected: 'Draw', found: 'Win'