QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#174560#7180. Forward-Capturing Pawnsucup-team1448AC ✓465ms124072kbC++146.4kb2023-09-10 09:31:482023-09-10 09:31:48

Judging History

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

  • [2023-09-10 09:31:48]
  • 评测
  • 测评结果:AC
  • 用时:465ms
  • 内存:124072kb
  • [2023-09-10 09:31:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define loop                                                                   \
    for (int bx = 0; bx < 8; ++bx)                                             \
        for (int by = 0; by < 8; ++by)                                         \
            for (int wx = 0; wx < 8; ++wx)                                     \
                for (int wy = 0; wy < 8; ++wy)                                 \
                    for (int px = 0; px < 8; ++px)                             \
                        for (int py = 0; py < 8; ++py)                         \
                            for (int pt = 0; pt < 3; ++pt)                     \
                                for (int nx = 0; nx < 2; ++nx)                 \
                                    if (valid(bx, by, wx, wy, px, py, pt, nx))

#define add(bx, by, wx, wy, px, py, pt, nx)                                    \
    if (valid(bx, by, wx, wy, px, py, pt, nx)) {                               \
        graph.link(id[bx][by][wx][wy][px][py][pt][nx], cur);                   \
        ++deg[cur];                                                            \
    }

const int V = (10 << 18) + 5, E = (128 << 18) + 5;

struct Graph {
    int cnt, head[V], nxt[E], to[E];
    struct Iter {
        Iter(Graph *g, int i) : g(g), i(i) {}
        Graph *g;
        int i;
        bool operator!=(Iter &o) { return i != o.i; }
        Iter operator++() {
            i = g->nxt[i];
            return *this;
        }
        int operator*() { return g->to[i]; }
        Iter begin() { return *this; }
        Iter end() { return {g, 0}; }
    };
    Iter operator[](int i) { return {this, head[i]}; }
    void link(int u, int v) {
        nxt[++cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt;
    }
};

// Position of black king, white king and white pawn;
// P/Q/R promoted from white pawn; next player is white/black
int tot, id[8][8][8][8][8][8][3][2];

// Check if a square is reachable by white pawn
bool reachable(int bx, int by, int wx, int wy, int px, int py, int pt, int x,
               int y) {
    if ((wx == x && wy == y) || (x == px && y == py)) return false;
    if (pt == 0) {
        return (x == px && y == py + 1) ||
               (x == px && y == 3 && py == 1 && !(bx == px && by == 2) &&
                !(wx == px && wy == 2));
    }
    if (pt == 1 || pt == 2) {
        if (x == px)
            return !(x == bx && ((y < by && by < py) || (y > by && by > py))) &&
                   !(x == wx && ((y < wy && wy < py) || (y > wy && wy > py)));
        if (y == py)
            return !(y == by && ((x < bx && bx < px) || (x > bx && bx > px))) &&
                   !(y == wy && ((x < wx && wx < px) || (x > wx && wx > px)));
    }
    if (pt == 1) {
        if (x - y == px - py)
            return !(x - y == bx - by &&
                     ((x < bx && bx < px) || (x > bx && bx > px))) &&
                   !(x - y == wx - wy &&
                     ((x < wx && wx < px) || (x > wx && wx > px)));
        if (x + y == px + py)
            return !(x + y == bx + by &&
                     ((x < bx && bx < px) || (x > bx && bx > px))) &&
                   !(x + y == wx + wy &&
                     ((x < wx && wx < px) || (x > wx && wx > px)));
    }
    return false;
}

// Check if black king is in check
bool check(int bx, int by, int wx, int wy, int px, int py, int pt) {
    return reachable(bx, by, wx, wy, px, py, pt, bx, by);
}

// Check if a position is valid
bool valid(int bx, int by, int wx, int wy, int px, int py, int pt, int nx) {
    if (bx < 0 || bx >= 8 || by < 0 || by >= 8) return false;
    if (wx < 0 || wx >= 8 || wy < 0 || wy >= 8) return false;
    if (px < 0 || px >= 8 || py < 0 || py >= 8) return false;
    if (pt == 0 && (py == 0 || py == 7)) return false;
    // If white is next, then black pawn is considered captured
    if (nx && bx == px && by == py) return false;
    if (wx == px && wy == py) return false;
    if (abs(bx - wx) <= 1 && abs(by - wy) <= 1) return false;
    if (!nx && reachable(bx, by, wx, wy, px, py, pt, bx, by)) return false;
    return true;
}

Graph graph;
int deg[V];
bool nxt[V], win[V];

const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1},
          dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    loop {
        id[bx][by][wx][wy][px][py][pt][nx] = tot;
        nxt[tot++] = nx;
    }
    loop {
        int cur = id[bx][by][wx][wy][px][py][pt][nx];
        if (nx == 0) {
            // Two single kings form a draw
            if (bx == px && by == py) continue;
            for (int i = 0; i < 8; ++i)
                add(bx, by, wx + dx[i], wy + dy[i], px, py, pt, 1);
            for (int x = 0; x < 8; ++x) {
                for (int y = 0; y < 8; ++y) {
                    if (reachable(bx, by, wx, wy, px, py, pt, x, y)) {
                        // Promotion
                        if (pt == 0 && y == 7) {
                            for (int t = 1; t < 3; ++t)
                                add(bx, by, wx, wy, x, y, t, 1);
                        } else
                            add(bx, by, wx, wy, x, y, pt, 1);
                    }
                }
            }
        } else
            for (int i = 0; i < 8; ++i)
                add(bx + dx[i], by + dy[i], wx, wy, px, py, pt, 0);
        // Stalemate if black king is not in check
        // Note that white king can also be stalemated
        if (deg[cur] == 0) win[cur] = check(bx, by, wx, wy, px, py, pt);
    }
    queue<int> q;
    for (int i = 0; i < tot; ++i)
        if (win[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            assert(v < V);
            if (win[v]) continue;
            if (!nxt[v] || --deg[v] == 0) {
                win[v] = true;
                q.push(v);
            }
        }
    }
    int t;
    scanf("%d", &t);
    getchar();
    while (t--) {
        int bx, by, wx, wy, px, py, nx;
        wx = getchar() - 'a';
        wy = getchar() - '1';
        getchar();
        px = getchar() - 'a';
        py = getchar() - '1';
        getchar();
        bx = getchar() - 'a';
        by = getchar() - '1';
        getchar();
        nx = getchar() == 'b';
        getchar();
        puts(win[id[bx][by][wx][wy][px][py][0][nx]] ? "Win" : "Draw");
    }
}

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

详细

Test #1:

score: 100
Accepted
time: 434ms
memory: 124072kb

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: 465ms
memory: 124044kb

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