QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267959 | #7180. Forward-Capturing Pawns | EWDEHSAMSWATERMELON | AC ✓ | 256ms | 73624kb | C++17 | 8.2kb | 2023-11-27 21:35:27 | 2023-11-27 21:35:27 |
Judging History
answer
// #define _GLIBCXX_DEBUG
// #define _GLIBCXX_DEBUG_PEDANTIC
#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
using pii = pair <int, int>;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
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;
}
}
constexpr int N = 8;
constexpr int FIELD = N * N;
int dp[FIELD][FIELD][FIELD][2];
// [white king][white pawn][black king][black/white]
pii getcord(int ind) {
return {ind / N, ind % N};
}
int getind(int x, int y) {
return x * N + y;
}
int dist(int x1, int y1, int x2, int y2) {
return max(abs(x1 - x2), abs(y1 - y2));
}
bool kingtakes(int k, int pos) {
auto [kx, ky] = getcord(k);
auto [px, py] = getcord(pos);
return dist(kx, ky, px, py) <= 1;
}
bool pawntakes(int k, int pos) {
auto [kx, ky] = getcord(k);
auto [px, py] = getcord(pos);
if (kx == 1) {
return pii{px, py} == pii{kx + 1, ky} || pii{px, py} == pii{kx + 2, ky};
}
return pii{px, py} == pii{kx + 1, ky};
}
bool checkgood(int wk, int wp, int bk, int mv) {
if (wp == wk) {
return false;
}
if (wp < N) {
return false;
}
if (kingtakes(wk, bk)) {
return false;
}
if (mv == 1 && pawntakes(wp, bk)) {
return false;
}
return true;
}
struct State {
int wk{};
int wp{};
int bk{};
int mv{};
State() = default;
State(int wk, int wp, int bk, int mv)
: wk(wk), wp(wp), bk(bk), mv(mv) { }
};
vector <State> g[FIELD][FIELD][FIELD][2];
int cnt[FIELD][FIELD][FIELD][2];
int conv(string s) {
return (s[1] - '1') * N + s[0] - 'a';
}
bool operator==(int a, string s) {
return a == conv(s);
}
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
queue <State> q;
for (int wk = 0; wk < FIELD; ++wk) {
for (int wp = 0; wp < FIELD; ++wp) {
for (int bk = 0; bk < FIELD; ++bk) {
for (int mv = 0; mv < 2; ++mv) {
if (checkgood(wk, wp, bk, mv)) {
if (wp / N == N - 1 && (mv == 1 || kingtakes(wk, wp) || !kingtakes(bk, wp))) {
dp[wk][wp][bk][mv] = 2;
}
if (bk == wp) {
dp[wk][wp][bk][mv] = 1;
}
if (dp[wk][wp][bk][mv]) {
q.emplace(wk, wp, bk, mv);
} else {
if (mv) { // white
{
// if (wk == conv("b6") && wp == conv("d7") && bk == conv("e7")) {
// cerr << "";
// }
auto [bx, by] = getcord(wk);
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (!dx && !dy) {
continue;
}
int x = bx + dx, y = by + dy;
if (min(x, y) < 0 || max(x, y) >= N) {
continue;
}
int nwk = getind(x, y);
if (checkgood(nwk, wp, bk, mv ^ 1)) {
g[nwk][wp][bk][mv ^ 1].emplace_back(wk, wp, bk, mv);
++cnt[wk][wp][bk][mv];
}
}
}
}
{
auto [bx, by] = getcord(wp);
if (bx == 1) {
if (checkgood(wk, wp + 2 * N, bk, mv ^ 1)) {
g[wk][wp + 2 * N][bk][mv ^ 1].emplace_back(wk, wp, bk, mv);
++cnt[wk][wp][bk][mv];
}
}
if (bx + 1 < N) {
if (checkgood(wk, wp + N, bk, mv ^ 1)) {
g[wk][wp + N][bk][mv ^ 1].emplace_back(wk, wp, bk, mv);
++cnt[wk][wp][bk][mv];
}
}
}
} else { // black
auto [bx, by] = getcord(bk);
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (!dx && !dy) {
continue;
}
int x = bx + dx, y = by + dy;
if (min(x, y) < 0 || max(x, y) >= N) {
continue;
}
int nbk = getind(x, y);
if (checkgood(wk, wp, nbk, mv ^ 1)) {
g[wk][wp][nbk][mv ^ 1].emplace_back(wk, wp, bk, mv);
++cnt[wk][wp][bk][mv];
}
}
}
}
}
}
}
}
}
}
while (!q.empty()) {
auto [wk, wp, bk, mv] = q.front();
q.pop();
// if (wk == conv("c7") && wp == conv("d7") && bk == conv("e7")) {
// cerr << "";
// }
for (auto [nwk, nwp, nbk, nmv] : g[wk][wp][bk][mv]) {
// if (nwk == conv("b6") && nwp == conv("d7") && nbk == conv("e7")) {
// cerr << "";
// }
if (!dp[nwk][nwp][nbk][nmv]) {
--cnt[nwk][nwp][nbk][nmv];
if (nmv == 0) {
if (!cnt[nwk][nwp][nbk][nmv]) {
dp[nwk][nwp][nbk][nmv] = 2;
}
if (dp[wk][wp][bk][mv] == 1) {
dp[nwk][nwp][nbk][nmv] = 1;
}
} else {
if (!cnt[nwk][nwp][nbk][nmv]) {
dp[nwk][nwp][nbk][nmv] = 1;
}
if (dp[wk][wp][bk][mv] == 2) {
dp[nwk][nwp][nbk][nmv] = 2;
}
}
if (dp[nwk][nwp][nbk][nmv]) {
q.emplace(nwk, nwp, nbk, nmv);
}
}
}
}
cerr << dp[conv("c7")][conv("d7")][conv("e7")][0] << " ";
cerr << dp[conv("c7")][conv("d7")][conv("e7")][1] << " ";
cerr << dp[conv("b6")][conv("d7")][conv("e7")][1] << " ";
int T;
cin >> T;
while (T--) {
string wk, wp, bk, mv;
cin >> wk >> wp >> bk >> mv;
int wk1 = conv(wk), wp1 = conv(wp), bk1 = conv(bk);
int mv1 = (mv == "b" ? 0 : 1);
if (dp[wk1][wp1][bk1][mv1] == 2) {
cout << "Win";
} else {
cout << "Draw";
}
cout << endl;
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 135ms
memory: 73624kb
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: 256ms
memory: 73528kb
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