QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267959#7180. Forward-Capturing PawnsEWDEHSAMSWATERMELONAC ✓256ms73624kbC++178.2kb2023-11-27 21:35:272023-11-27 21:35:27

Judging History

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

  • [2023-11-27 21:35:27]
  • 评测
  • 测评结果:AC
  • 用时:256ms
  • 内存:73624kb
  • [2023-11-27 21:35:27]
  • 提交

answer

// #define _GLIBCXX_DEBUG
// #define _GLIBCXX_DEBUG_PEDANTIC
#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
  
using namespace std;
//#define int long long
using pii = pair <int, int>;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
  
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;
    }
}    

constexpr int N = 8;
constexpr int FIELD = N * N;

int dp[FIELD][FIELD][FIELD][2];
// [white king][white pawn][black king][black/white]

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

int getind(int x, int y) {
    return x * N + y;
}

int dist(int x1, int y1, int x2, int y2) {
    return max(abs(x1 - x2), abs(y1 - y2));
}

bool kingtakes(int k, int pos) {
    auto [kx, ky] = getcord(k);
    auto [px, py] = getcord(pos);
    return dist(kx, ky, px, py) <= 1;
}

bool pawntakes(int k, int pos) {
    auto [kx, ky] = getcord(k);
    auto [px, py] = getcord(pos);
    if (kx == 1) {
        return pii{px, py} == pii{kx + 1, ky} || pii{px, py} == pii{kx + 2, ky};
    }
    return pii{px, py} == pii{kx + 1, ky};
}

bool checkgood(int wk, int wp, int bk, int mv) {
    if (wp == wk) {
        return false;
    }
    if (wp < N) {
        return false;
    }
    if (kingtakes(wk, bk)) {
        return false;
    }
    if (mv == 1 && pawntakes(wp, bk)) {
        return false;
    }
    return true;
}

struct State {
    int wk{};
    int wp{};
    int bk{};
    int mv{};

    State() = default;
    State(int wk, int wp, int bk, int mv) 
        : wk(wk), wp(wp), bk(bk), mv(mv) { }
};
    
vector <State> g[FIELD][FIELD][FIELD][2];
int cnt[FIELD][FIELD][FIELD][2];

int conv(string s) {
    return (s[1] - '1') * N + s[0] - 'a';
}

bool operator==(int a, string s) {
    return a == conv(s);
}

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
    queue <State> q;
    for (int wk = 0; wk < FIELD; ++wk) {
        for (int wp = 0; wp < FIELD; ++wp) {
            for (int bk = 0; bk < FIELD; ++bk) {
                for (int mv = 0; mv < 2; ++mv) {
                    if (checkgood(wk, wp, bk, mv)) {
                        if (wp / N == N - 1 && (mv == 1 || kingtakes(wk, wp) || !kingtakes(bk, wp))) {
                            dp[wk][wp][bk][mv] = 2;
                        }
                        if (bk == wp) {
                            dp[wk][wp][bk][mv] = 1;
                        }
                        if (dp[wk][wp][bk][mv]) {
                            q.emplace(wk, wp, bk, mv);
                        } else {
                            if (mv) { // white
                                {
                                    // if (wk == conv("b6") && wp == conv("d7") && bk == conv("e7")) {
                                    //     cerr << "";
                                    // }
                                    auto [bx, by] = getcord(wk);
                                    for (int dx = -1; dx <= 1; ++dx) {
                                        for (int dy = -1; dy <= 1; ++dy) {
                                            if (!dx && !dy) {
                                                continue;
                                            }
                                            int x = bx + dx, y = by + dy;
                                            if (min(x, y) < 0 || max(x, y) >= N) {
                                                continue;
                                            }
                                            int nwk = getind(x, y);
                                            if (checkgood(nwk, wp, bk, mv ^ 1)) {
                                                g[nwk][wp][bk][mv ^ 1].emplace_back(wk, wp, bk, mv);
                                                ++cnt[wk][wp][bk][mv];
                                            }
                                        }
                                    }
                                }
                                {
                                    auto [bx, by] = getcord(wp);
                                    if (bx == 1) {    
                                        if (checkgood(wk, wp + 2 * N, bk, mv ^ 1)) {
                                            g[wk][wp + 2 * N][bk][mv ^ 1].emplace_back(wk, wp, bk, mv);
                                            ++cnt[wk][wp][bk][mv];
                                        }
                                    }
                                    if (bx + 1 < N) {
                                        if (checkgood(wk, wp + N, bk, mv ^ 1)) {
                                            g[wk][wp + N][bk][mv ^ 1].emplace_back(wk, wp, bk, mv);
                                            ++cnt[wk][wp][bk][mv];
                                        }
                                    }
                                }
                            } else { // black
                                auto [bx, by] = getcord(bk);
                                for (int dx = -1; dx <= 1; ++dx) {
                                    for (int dy = -1; dy <= 1; ++dy) {
                                        if (!dx && !dy) {
                                            continue;
                                        }
                                        int x = bx + dx, y = by + dy;
                                        if (min(x, y) < 0 || max(x, y) >= N) {
                                            continue;
                                        }
                                        int nbk = getind(x, y);
                                        if (checkgood(wk, wp, nbk, mv ^ 1)) {
                                            g[wk][wp][nbk][mv ^ 1].emplace_back(wk, wp, bk, mv);
                                            ++cnt[wk][wp][bk][mv];
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    while (!q.empty()) {
        auto [wk, wp, bk, mv] = q.front();
        q.pop();
        // if (wk == conv("c7") && wp == conv("d7") && bk == conv("e7")) {
        //     cerr << "";
        // }
        for (auto [nwk, nwp, nbk, nmv] : g[wk][wp][bk][mv]) {
                // if (nwk == conv("b6") && nwp == conv("d7") && nbk == conv("e7")) {
                //     cerr << "";
                // }
            if (!dp[nwk][nwp][nbk][nmv]) {
                --cnt[nwk][nwp][nbk][nmv];
                if (nmv == 0) {
                    if (!cnt[nwk][nwp][nbk][nmv]) {
                        dp[nwk][nwp][nbk][nmv] = 2;
                    }
                    if (dp[wk][wp][bk][mv] == 1) {
                        dp[nwk][nwp][nbk][nmv] = 1;
                    }
                } else {
                    if (!cnt[nwk][nwp][nbk][nmv]) {
                        dp[nwk][nwp][nbk][nmv] = 1;
                    }
                    if (dp[wk][wp][bk][mv] == 2) {
                        dp[nwk][nwp][nbk][nmv] = 2;
                    }
                }
                if (dp[nwk][nwp][nbk][nmv]) {
                    q.emplace(nwk, nwp, nbk, nmv); 
                }
            }
        }
    }
    cerr << dp[conv("c7")][conv("d7")][conv("e7")][0] << " ";
    cerr << dp[conv("c7")][conv("d7")][conv("e7")][1] << " ";
    cerr << dp[conv("b6")][conv("d7")][conv("e7")][1] << " ";
    int T;
    cin >> T;
    while (T--) {
        string wk, wp, bk, mv;
        cin >> wk >> wp >> bk >> mv;
        int wk1 = conv(wk), wp1 = conv(wp), bk1 = conv(bk);
        int mv1 = (mv == "b" ? 0 : 1);
        if (dp[wk1][wp1][bk1][mv1] == 2) {
            cout << "Win";
        } else {
            cout << "Draw";
        }
        cout << endl;
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 135ms
memory: 73624kb

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: 256ms
memory: 73528kb

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