QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#165340 | #7180. Forward-Capturing Pawns | ucup-team087# | WA | 134ms | 58748kb | C++14 | 8.0kb | 2023-09-05 17:35:48 | 2023-09-05 17:35:49 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
int lens[64];
int adj[64][8];
// White king, White pawn, Black king
int V;
int ids[64][64][64][2];
vector<int> turnOf;
vector<vector<int>> graph, hparg;
bool adjacent(int a, int b) {
const int ax = a / 8, ay = a % 8;
const int bx = b / 8, by = b % 8;
return (abs(ax - bx) <= 1 && abs(ay - by) <= 1);
}
bool checkedA(int a, int /*b*/, int c) {
if (adjacent(a, c)) return true;
return false;
}
bool checkedC(int a, int b, int c) {
const int ax = a / 8, ay = a % 8;
const int bx = b / 8, by = b % 8;
const int cx = c / 8, cy = c % 8;
if (adjacent(a, c)) return true;
if (by == cy) {
if (bx - 1 == cx) return true;
if (bx == 6 && cx == 4 && make_pair(ax, ay) != make_pair(5, by)) return true;
}
return false;
}
bool isReasonable(int a, int b, int c, int t) {
// const int ax = a / 8, ay = a % 8;
const int bx = b / 8/*, by = b % 8*/;
// const int cx = c / 8, cy = c % 8;
// 1
if (a == b) return false;
if (a == c) return false;
if (b == c) return false;
// 2
if (bx == 0 || bx == 7) return false;
// 3
if (t == 0) {
if (checkedC(a, b, c)) return false;
} else {
if (checkedA(a, b, c)) return false;
}
return true;
}
bool checkedCRook(int a, int b, int c) {
const int ax = a / 8, ay = a % 8;
const int bx = b / 8, by = b % 8;
const int cx = c / 8, cy = c % 8;
if (adjacent(a, c)) return true;
if (bx == cx && !(ax == bx && (ay - by) * (ay - cy) < 0)) return true;
if (by == cy && !(ay == by && (ax - bx) * (ax - cx) < 0)) return true;
return false;
}
bool rookStalemate(int a, int b, int c) {
// check
if (checkedCRook(a, b, c)) return false;
// mate
for (int h = 0; h < lens[c]; ++h) {
const int cc = adj[c][h];
assert(a != cc);
if (b == cc) {
if (!adjacent(a, cc)) return false;
} else {
if (!checkedCRook(a, b, cc)) return false;
}
}
cerr<<"rookStalemate "<<make_pair(a/8,a%8)<<" "<<make_pair(b/8,b%8)<<" "<<make_pair(c/8,c%8)<<endl;
return true;
}
int readPiece() {
char buf[10];
scanf("%s", buf);
const int x = '8' - buf[1];
const int y = buf[0] - 'a';
assert(0 <= x); assert(x < 8);
assert(0 <= y); assert(y < 8);
return x * 8 + y;
}
int readTurn() {
char c;
scanf(" %c", &c);
return (c == 'b') ? 1 : 0;
}
int main() {
memset(adj, ~0, sizeof(adj));
for (int a = 0; a < 64; ++a) {
const int x = a / 8, y = a % 8;
for (int dx = -1; dx <= +1; ++dx) for (int dy = -1; dy <= +1; ++dy) if (dx || dy) {
const int xx = x + dx;
const int yy = y + dy;
if (0 <= xx && xx < 8 && 0 <= yy && yy < 8) {
const int b = xx * 8 + yy;
adj[a][lens[a]++] = b;
}
}
}
V = 2;
memset(ids, ~0, sizeof(ids));
turnOf = {1, 1};
for (int a = 0; a < 64; ++a) for (int b = 0; b < 64; ++b) for (int c = 0; c < 64; ++c) {
for (int t = 0; t < 2; ++t) {
if (isReasonable(a, b, c, t)) {
ids[a][b][c][t] = V++;
turnOf.push_back(t);
}
}
}
cerr<<"V = "<<V<<endl;
graph.assign(V, {});
graph[1].push_back(1);
for (int a = 0; a < 64; ++a) for (int b = 0; b < 64; ++b) for (int c = 0; c < 64; ++c) {
const int ax = a / 8, ay = a % 8;
const int bx = b / 8, by = b % 8;
const int cx = c / 8, cy = c % 8;
for (int t = 0; t < 2; ++t) {
const int u = ids[a][b][c][t];
if (~u) {
if (t == 0) {
// king
for (int h = 0; h < lens[a]; ++h) {
const int aa = adj[a][h];
const int v = ids[aa][b][c][t ^ 1];
if (~v) {
// if(u==90324)cerr<<make_pair(aa/8,aa%8)<<" "<<v<<endl;
graph[u].push_back(v);
}
}
// pawn
for (int bbx = bx - 1; bbx >= ((bx == 6) ? 4 : (bx - 1)); --bbx) {
if (bx == 6 && bbx == 4 && (make_pair(ax, ay) == make_pair(5, by) || make_pair(cx, cy) == make_pair(5, by))) {
// jump
// cerr<<"jump "<<make_pair(ax,ay)<<" "<<make_pair(bx,by)<<" "<<make_pair(cx,cy)<<endl;
continue;
}
const int bby = by;
const int bb = bbx * 8 + bby;
const int v = ids[a][bb][c][t ^ 1];
if (~v) {
graph[u].push_back(v);
} else if (bbx == 0) {
// promotion
// if(u==54374||u==54376||u==54386||u==54394||u==54396)cerr<<__LINE__<<" promo "<<u<<" "<<make_pair(bbx,bby)<<endl;
if (adjacent(bb, c)) {
if (adjacent(bb, a)) {
if (!rookStalemate(a, bb, c)) graph[u].push_back(0);
} else {
// useless
}
} else {
if (!rookStalemate(a, bb, c)) graph[u].push_back(0);
}
}
}
} else {
// king
for (int h = 0; h < lens[c]; ++h) {
const int cc = adj[c][h];
const int v = ids[a][b][cc][t ^ 1];
if (~v) {
graph[u].push_back(v);
} else if (cc == b) {
// capture
if (adjacent(cc, a)) {
// invalid
} else {
graph[u].push_back(1);
}
}
}
// if(u==54385)cerr<<__LINE__<<" "<<graph[u]<<endl;
if (graph[u].empty()) {
// checkmate or stalemate
if (!checkedC(a, b, c)) {
cerr<<"stalemate "<<make_pair(ax,ay)<<" "<<make_pair(bx,by)<<" "<<make_pair(cx,cy)<<endl;
graph[u].push_back(1);
}
}
}
}
}
}
vector<int> deg(V);
hparg.assign(V, {});
for (int u = 0; u < V; ++u) {
deg[u] = graph[u].size();
for (const int v : graph[u]) {
hparg[v].push_back(u);
}
}
vector<int> ans(V, 0);
queue<int> que;
for (int u = 0; u < V; ++u) if (turnOf[u] == 1 && deg[u] == 0) {
que.push(u);
}
for (; !que.empty(); ) {
// v: Win
const int v = que.front();
que.pop();
assert(!ans[v]);
ans[v] = 1;
for (const int u : hparg[v]) {
if (turnOf[u] == 0) {
if (deg[u]) {
que.push(u);
}
deg[u] = 0;
} else {
if (--deg[u] == 0) {
que.push(u);
}
}
}
}
int sumAns=0;for(int u=0;u<V;++u)sumAns+=ans[u];cerr<<"sumAns = "<<sumAns<<endl;
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
const int a = readPiece();
const int b = readPiece();
const int c = readPiece();
const int t = readTurn();
assert(isReasonable(a, b, c, t));
const int u = ids[a][b][c][t];
// cerr<<a<<" "<<b<<" "<<c<<" "<<t<<": "<<u<<endl;
assert(~u);
puts(ans[u] ? "Win" : "Draw");
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 104ms
memory: 58748kb
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: 134ms
memory: 58660kb
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:
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 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:
wrong answer 1st lines differ - expected: 'Draw', found: 'Win'