QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414800#7180. Forward-Capturing PawnspandapythonerAC ✓288ms134896kbC++205.9kb2024-05-19 19:05:362024-05-19 19:05:36

Judging History

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

  • [2024-05-19 19:05:36]
  • 评测
  • 测评结果:AC
  • 用时:288ms
  • 内存:134896kb
  • [2024-05-19 19:05:36]
  • 提交

answer

// #pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);


struct pos {
    int wkx, wky;
    int wpx, wpy;
    int bkx, bky;
    char mv;

    pos() {}
    pos(int wkx, int wky, int wpx, int wpy, int bkx, int bky, char mv) :
        wkx(wkx), wky(wky), wpx(wpx), wpy(wpy), bkx(bkx), bky(bky), mv(mv) {
    }
    pos(string s) {
        wkx = s[0] - 'a' + 1;
        wky = s[1] - '1' + 1;
        wpx = s[3] - 'a' + 1;
        wpy = s[4] - '1' + 1;
        bkx = s[6] - 'a' + 1;
        bky = s[7] - '1' + 1;
        mv = s[9];
    }


    bool chck(int x) {
        return 1 <= x and x <= 8;
    }

    bool reasonable() {
        if (!(chck(wkx) and chck(wky) and chck(wpx) and chck(wpy) and chck(bkx) and chck(bky))) {
            return false;
        }
        if (abs(wkx - bkx) <= 1 and abs(wky - bky) <= 1) {
            return false;
        }
        if (wpy == 1) {
            return false;
        }
        if (wpx == bkx and wpy + 1 == bky and mv == 'w') {
            return false;
        }
        if (wpy == 2 and wpx == bkx and wpy + 2 == bky and mv == 'w') {
            return false;
        }
        pair<int, int> wk = { wkx, wky };
        pair<int, int> wp = { wpx, wpy };
        pair<int, int> bk = { bkx, bky };
        if (wk == wp or wk == bk) {
            return false;
        }
        if (wp == bk and mv == 'b') {
            return false;
        }
        return true;
    }

    ll hsh() const {
        array<int, 7> arr({ wkx, wky, wpx, wpy, bkx, bky, mv });
        int rs = 0;
        for (int i = 0; i < 7; i += 1) {
            if (i == 6) {
                rs *= 2;
                if (mv == 'b') {
                    rs += 1;
                } else {
                    rs += 0;
                }
            } else {
                rs *= 8;
                rs += arr[i] - 1;
            }
        }
        return rs;
    }
};

bool operator<(const pos& a, const pos& b) {
    return array<int, 7>({ a.wkx, a.wky, a.wpx, a.wpy, a.bkx, a.bky, a.mv }) <
        array<int, 7>({ b.wkx, b.wky, b.wpx, b.wpy, b.bkx, b.bky, b.mv });
}

const int N = 8 * 8 * 8 * 8 * 8 * 8 * 2 + 1000;

bool good[N];
pos poss[N];
int cntout[N];
vector<pos> gin[N];
bool win[N];

void build() {
    for (int wkx = 1; wkx <= 8; wkx += 1) {
        for (int wky = 1; wky <= 8; wky += 1) {
            for (int wpx = 1; wpx <= 8; wpx += 1) {
                for (int wpy = 1; wpy <= 8; wpy += 1) {
                    for (int bkx = 1; bkx <= 8; bkx += 1) {
                        for (int bky = 1; bky <= 8; bky += 1) {
                            for (char mv : {'b', 'w'}) {
                                pos p{ wkx, wky, wpx, wpy, bkx, bky, mv };
                                if (p.reasonable()) {
                                    good[p.hsh()] = true;
                                    poss[p.hsh()] = p;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    queue<pos> q;
    for (int i = 0; i < N; i += 1) {
        auto p = poss[i];
        if (p.mv == 'w') {
            if (p.wpx == p.bkx and p.wpy == p.bky) {
                continue;
            }
            if (p.wpy == 8) {
                q.push(p);
                win[p.hsh()] = true;
            }
            for (int dx = -1; dx <= 1; dx += 1) {
                for (int dy = -1; dy <= 1; dy += 1) {
                    if (dx == 0 and dy == 0) {
                        continue;
                    }
                    auto np = p;
                    np.mv = 'b';
                    np.wkx += dx;
                    np.wky += dy;
                    if (np.reasonable()) {
                        cntout[p.hsh()] += 1;
                        gin[np.hsh()].push_back(p);
                    }
                }
            }
            for (int dy = 1; dy <= 2; dy += 1) {
                if (dy == 2 and p.wpy != 2) {
                    continue;
                }
                auto np = p;
                np.mv = 'b';
                np.wpy += dy;
                if (np.reasonable()) {
                    cntout[p.hsh()] += 1;
                    gin[np.hsh()].push_back(p);
                }
            }
        } else {
            for (int dx = -1; dx <= 1; dx += 1) {
                for (int dy = -1; dy <= 1; dy += 1) {
                    if (dx == 0 and dy == 0) {
                        continue;
                    }
                    auto np = p;
                    np.mv = 'w';
                    np.bkx += dx;
                    np.bky += dy;
                    if (np.reasonable()) {
                        cntout[p.hsh()] += 1;
                        gin[np.hsh()].push_back(p);
                    }
                }
            }
        }
    }
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        for (auto to : gin[p.hsh()]) {
            if (win[to.hsh()]) {
                continue;
            }
            cntout[to.hsh()] -= 1;
            if (cntout[to.hsh()] == 0 or to.mv == 'w') {
                q.push(to);
                win[to.hsh()] = true;
            }
        }
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    build();
    int t;
    cin >> t;
    string s;
    getline(cin, s);
    while (t--) {
        getline(cin, s);
        pos p(s);
        assert(p.reasonable());
        if (win[p.hsh()]) {
            cout << "Win" << "\n";
        } else {
            cout << "Draw" << "\n";
        }
    }
    return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 251ms
memory: 134896kb

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: 288ms
memory: 134860kb

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