QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249143 | #7180. Forward-Capturing Pawns | EWDEHSAMSWATERMELON | WA | 102ms | 9272kb | C++20 | 6.2kb | 2023-11-12 01:28:00 | 2023-11-12 01:28:01 |
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 (mv && wp / N == N - 1) {
if (wk == convpos("a2") && bk == convpos("e7") && wp == convpos("d8")) {
cerr << "";
}
if (!checkkingattack(bk, wp) || checkkingattack(wk, wp)) {
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 (win(wk, bk, wp, mv)) {
used[wk][bk][wp][mv] = 2;
dp[wk][bk][wp][mv] = 0;
return 0;
}
if (bk == wp) {
dp[wk][bk][wp][mv] = 1;
used[wk][bk][wp][mv] = 2;
return 1;
}
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)) {
if (cell == 0 && wk == convpos("a2") && bk == convpos("e7") && wp == convpos("d7")) {
cerr << "";
}
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 + 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 BUY
freopen("inputik.txt", "r", stdin);
freopen("outputik.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: 100
Accepted
time: 8ms
memory: 9272kb
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: 102ms
memory: 9072kb
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 Draw Draw Win Draw Win Win Win Win Win Draw Draw Draw Win Draw Draw Draw Win Draw Win Draw Win Draw Win Draw Draw Draw Win Draw Win Draw Draw Draw Win Draw Win Win Draw Draw Draw Draw Win Draw Win Draw Win Draw Draw Draw Win Draw Win Draw Win Draw Draw Draw Win Draw Win Draw Draw Draw...
result:
wrong answer 4th lines differ - expected: 'Win', found: 'Draw'