QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249143#7180. Forward-Capturing PawnsEWDEHSAMSWATERMELONWA 102ms9272kbC++206.2kb2023-11-12 01:28:002023-11-12 01:28:01

Judging History

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

  • [2023-11-12 01:28:01]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:9272kb
  • [2023-11-12 01:28:00]
  • 提交

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 (mv && wp / N == N - 1) {
        if (wk == convpos("a2") && bk == convpos("e7") && wp == convpos("d8")) {
            cerr << "";
        }
        if (!checkkingattack(bk, wp) || checkkingattack(wk, wp)) {
            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 (win(wk, bk, wp, mv)) {
        used[wk][bk][wp][mv] = 2;
        dp[wk][bk][wp][mv] = 0;
        return 0;
    }
    if (bk == wp) {
        dp[wk][bk][wp][mv] = 1;
        used[wk][bk][wp][mv] = 2;
        return 1;
    }
    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)) {
                        if (cell == 0 && wk == convpos("a2") && bk == convpos("e7") && wp == convpos("d7")) {
                            cerr << "";
                        }
                        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 + 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 BUY
    freopen("inputik.txt", "r", stdin);
    freopen("outputik.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: 100
Accepted
time: 8ms
memory: 9272kb

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: -100
Wrong Answer
time: 102ms
memory: 9072kb

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

result:

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