QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#174560 | #7180. Forward-Capturing Pawns | ucup-team1448 | AC ✓ | 465ms | 124072kb | C++14 | 6.4kb | 2023-09-10 09:31:48 | 2023-09-10 09:31:48 |
Judging History
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