QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252694 | #7180. Forward-Capturing Pawns | EWDEHSAMSWATERMELON | WA | 8ms | 9532kb | C++17 | 5.9kb | 2023-11-16 03:31:52 | 2023-11-16 03:31:53 |
Judging History
answer
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
using pii = pair<int, int>;
#define ff first
#define ss second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
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;
}
}
const int FIELD = 64;
int used[FIELD][FIELD][FIELD + 1][2];
int dp[FIELD][FIELD][FIELD + 1][2];
int BAD[10][10];
constexpr const int N = 8;
pii getcord(int pos) {
return {pos / N, pos % N};
}
int getpos(int i, int j) {
return i * N + j;
}
bool checkpawnattack(int pawn, int cell) {
auto [pi, pj] = getcord(pawn);
if (pi == 1) {
return getpos(pi + 1, pj) == cell ||
getpos(pi + 2, pj) == cell;
} else {
return getpos(pi + 1, pj) == cell;
}
}
int dist(int cell1, int cell2) {
auto [i1, j1] = getcord(cell1);
auto [i2, j2] = getcord(cell2);
return max(abs(i1 - i2), abs(j1 - j2));
}
int convpos(string t) {
return N * (t[1] - '1') + (t[0] - 'a');
}
bool checkkingattack(int king, int cell) {
return dist(king, cell) < 2;
}
bool win(int wk, int bk, int wp, int mv) {
if (wp / N == N - 1) {
if (!checkkingattack(bk, wp) || checkkingattack(wk, wp)) {
cerr << "";
return true;
}
return false;
}
return false;
}
bool checkpos(int wk, int bk, int wp, int mv) {
if (wp < N || wk == bk || wk == wp) {
return false;
}
if (!mv) {
if (checkkingattack(wk, bk)) {
return false;
}
if (checkpawnattack(wp, bk)) {
return false;
}
}
return true;
}
int calc(int wk, int bk, int wp, int mv) {
if (used[wk][bk][wp][mv] == 1) {
return -1;
}
if (used[wk][bk][wp][mv] == 2) {
return dp[wk][bk][wp][mv];
}
// if (checkDraw(WKpos, BKpos, WPpos, move)) {
// used[WKpos][BKpos][WPpos][move] = 2;
// dp[WKpos][BKpos][WPpos][move] = move;
// return 0;
// }
used[wk][bk][wp][mv] = 1;
if (bk == wp) {
dp[wk][bk][wp][mv] = 1;
used[wk][bk][wp][mv] = 2;
return 1;
}
if (win(wk, bk, wp, mv)) {
used[wk][bk][wp][mv] = 2;
dp[wk][bk][wp][mv] = 0;
return 0;
}
if (mv) {
bool flag = false;
auto [bi, bj] = getcord(bk);
dp[wk][bk][wp][mv] = 0;
for (int dx = 1; dx >= -1; --dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (!dx && !dy) {
continue;
}
int a = dx + bi;
int b = dy + bj;
if (min(a, b) < 0 || max(a, b) >= N) {
continue;
}
int cell = getpos(a, b);
if (!checkkingattack(wk, cell) && !checkpawnattack(wp, cell)) {
flag = true;
if (checkpos(wk, cell, wp, 1 - mv)) {
int r = calc(wk, cell, wp, 1 - mv);
if (r == 1) {
dp[wk][bk][wp][mv] = 1;
break;
}
}
}
}
}
if (!flag) {
dp[wk][bk][wp][mv] = 1;
used[wk][bk][wp][mv] = 2;
return 1;
}
used[wk][bk][wp][mv] = 2;
return dp[wk][bk][wp][mv];
} else {
bool flag = false;
auto [wi, wj] = getcord(wk);
dp[wk][bk][wp][mv] = 1;
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (!dx && !dy) {
continue;
}
int cell = wk + dx * N + dy;
int a = dx + wi;
int b = dy + wj;
if (min(a, b) < 0 || max(a, b) >= N) {
continue;
}
if (!checkkingattack(bk, cell)) {
flag = true;
if (checkpos(cell, bk, wp, 1 - mv)) {
int r = calc(cell, bk, wp, 1 - mv);
if (r == 0) {
dp[wk][bk][wp][mv] = 0;
break;
}
}
}
}
}
auto [pi, pj] = getcord(wp);
if (pi + 1 < N) {
int cell = wp + N;
if (checkpos(wk, bk, cell, 1 - mv)) {
int r = calc(wk, bk, cell, 1 - mv);
if (!r) {
dp[wk][bk][wp][mv] = 0;
}
}
if (pi == 1) {
cell = cell + 2 * N;
if (checkpos(wk, bk, cell, 1 - mv)) {
int r = calc(wk, bk, cell, 1 - mv);
if (!r) {
dp[wk][bk][wp][mv] = 0;
}
}
}
}
used[wk][bk][wp][mv] = 2;
return dp[wk][bk][wp][mv];
}
}
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
int n;
cin >> n;
while (n--) {
string wk, wp, bk;
cin >> wk >> wp >> bk;
int wk1 = convpos(wk);
int wp1 = convpos(wp);
int bk1 = convpos(bk);
string mv;
cin >> mv;
int mv1 = 0;
if (mv == "b") {
mv1 = 1;
}
int t = calc(wk1, bk1, wp1, mv1);
if (t) {
cout << "Draw\n";
} else {
cout << "Win\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 9532kb
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 Win Draw
result:
wrong answer 5th lines differ - expected: 'Draw', found: 'Win'