QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414800 | #7180. Forward-Capturing Pawns | pandapythoner | AC ✓ | 288ms | 134896kb | C++20 | 5.9kb | 2024-05-19 19:05:36 | 2024-05-19 19:05:36 |
Judging History
answer
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e18;
mt19937 rnd(234);
struct pos {
int wkx, wky;
int wpx, wpy;
int bkx, bky;
char mv;
pos() {}
pos(int wkx, int wky, int wpx, int wpy, int bkx, int bky, char mv) :
wkx(wkx), wky(wky), wpx(wpx), wpy(wpy), bkx(bkx), bky(bky), mv(mv) {
}
pos(string s) {
wkx = s[0] - 'a' + 1;
wky = s[1] - '1' + 1;
wpx = s[3] - 'a' + 1;
wpy = s[4] - '1' + 1;
bkx = s[6] - 'a' + 1;
bky = s[7] - '1' + 1;
mv = s[9];
}
bool chck(int x) {
return 1 <= x and x <= 8;
}
bool reasonable() {
if (!(chck(wkx) and chck(wky) and chck(wpx) and chck(wpy) and chck(bkx) and chck(bky))) {
return false;
}
if (abs(wkx - bkx) <= 1 and abs(wky - bky) <= 1) {
return false;
}
if (wpy == 1) {
return false;
}
if (wpx == bkx and wpy + 1 == bky and mv == 'w') {
return false;
}
if (wpy == 2 and wpx == bkx and wpy + 2 == bky and mv == 'w') {
return false;
}
pair<int, int> wk = { wkx, wky };
pair<int, int> wp = { wpx, wpy };
pair<int, int> bk = { bkx, bky };
if (wk == wp or wk == bk) {
return false;
}
if (wp == bk and mv == 'b') {
return false;
}
return true;
}
ll hsh() const {
array<int, 7> arr({ wkx, wky, wpx, wpy, bkx, bky, mv });
int rs = 0;
for (int i = 0; i < 7; i += 1) {
if (i == 6) {
rs *= 2;
if (mv == 'b') {
rs += 1;
} else {
rs += 0;
}
} else {
rs *= 8;
rs += arr[i] - 1;
}
}
return rs;
}
};
bool operator<(const pos& a, const pos& b) {
return array<int, 7>({ a.wkx, a.wky, a.wpx, a.wpy, a.bkx, a.bky, a.mv }) <
array<int, 7>({ b.wkx, b.wky, b.wpx, b.wpy, b.bkx, b.bky, b.mv });
}
const int N = 8 * 8 * 8 * 8 * 8 * 8 * 2 + 1000;
bool good[N];
pos poss[N];
int cntout[N];
vector<pos> gin[N];
bool win[N];
void build() {
for (int wkx = 1; wkx <= 8; wkx += 1) {
for (int wky = 1; wky <= 8; wky += 1) {
for (int wpx = 1; wpx <= 8; wpx += 1) {
for (int wpy = 1; wpy <= 8; wpy += 1) {
for (int bkx = 1; bkx <= 8; bkx += 1) {
for (int bky = 1; bky <= 8; bky += 1) {
for (char mv : {'b', 'w'}) {
pos p{ wkx, wky, wpx, wpy, bkx, bky, mv };
if (p.reasonable()) {
good[p.hsh()] = true;
poss[p.hsh()] = p;
}
}
}
}
}
}
}
}
queue<pos> q;
for (int i = 0; i < N; i += 1) {
auto p = poss[i];
if (p.mv == 'w') {
if (p.wpx == p.bkx and p.wpy == p.bky) {
continue;
}
if (p.wpy == 8) {
q.push(p);
win[p.hsh()] = true;
}
for (int dx = -1; dx <= 1; dx += 1) {
for (int dy = -1; dy <= 1; dy += 1) {
if (dx == 0 and dy == 0) {
continue;
}
auto np = p;
np.mv = 'b';
np.wkx += dx;
np.wky += dy;
if (np.reasonable()) {
cntout[p.hsh()] += 1;
gin[np.hsh()].push_back(p);
}
}
}
for (int dy = 1; dy <= 2; dy += 1) {
if (dy == 2 and p.wpy != 2) {
continue;
}
auto np = p;
np.mv = 'b';
np.wpy += dy;
if (np.reasonable()) {
cntout[p.hsh()] += 1;
gin[np.hsh()].push_back(p);
}
}
} else {
for (int dx = -1; dx <= 1; dx += 1) {
for (int dy = -1; dy <= 1; dy += 1) {
if (dx == 0 and dy == 0) {
continue;
}
auto np = p;
np.mv = 'w';
np.bkx += dx;
np.bky += dy;
if (np.reasonable()) {
cntout[p.hsh()] += 1;
gin[np.hsh()].push_back(p);
}
}
}
}
}
while (!q.empty()) {
auto p = q.front();
q.pop();
for (auto to : gin[p.hsh()]) {
if (win[to.hsh()]) {
continue;
}
cntout[to.hsh()] -= 1;
if (cntout[to.hsh()] == 0 or to.mv == 'w') {
q.push(to);
win[to.hsh()] = true;
}
}
}
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
build();
int t;
cin >> t;
string s;
getline(cin, s);
while (t--) {
getline(cin, s);
pos p(s);
assert(p.reasonable());
if (win[p.hsh()]) {
cout << "Win" << "\n";
} else {
cout << "Draw" << "\n";
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 251ms
memory: 134896kb
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: 288ms
memory: 134860kb
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