QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210976 | #7180. Forward-Capturing Pawns | ucup-team191 | WA | 980ms | 186664kb | C++14 | 6.0kb | 2023-10-11 22:21:02 | 2023-10-11 22:21:02 |
Judging History
answer
#include <bits/stdc++.h>
#define X first
#define Y second
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int MAXN=100*100*100*2,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int cnt;
int deg[MAXN], sol[MAXN];
vector <int> v[MAXN], r[MAXN];
queue <int> q;
struct board {
int wx, wy, bx, by, px, py, turn;
board () {
}
board (int _wx, int _wy, int _bx, int _by, int _px, int _py, int _turn) {
wx = _wx; wy = _wy;
bx = _bx; by = _by;
px = _px; py = _py;
turn = _turn;
}
int get_hash () {
int h = 0;
h = h * 9 + wx;
h = h * 9 + wy;
h = h * 9 + bx;
h = h * 9 + by;
h = h * 9 + px;
h = h * 9 + py;
h = h * 9 + turn;
return h;
}
} state[MAXN];
map <int, int> mp;
bool valid (int wx, int wy, int bx, int by, int px, int py, int turn) {
if (!(0 <= wx && wx <= 7)) return 0;
if (!(0 <= wy && wy <= 7)) return 0;
if (!(0 <= bx && bx <= 7)) return 0;
if (!(0 <= by && by <= 7)) return 0;
if (!(0 <= px && px <= 7)) return 0;
if (!(1 <= py && py <= 8)) return 0;
if (abs(wx - bx) <= 1 && abs(wy - by) <= 1) return 0;
if (py <= 7) {
if (wx == px && wy == py) return 0;
if (bx == px && by == py) return 0;
if (turn == 0) {
if (bx == px && by == py + 1) return 0;
if (bx == px && by == py + 2) return 0;
}
}
return 1;
}
bool promotion_win (int wx, int wy, int bx, int by, int px, int py, int turn) {
if (turn == 0) return 0;
if (py != 7) return 0;
if (abs(px - wx) <= 1 && abs(py - wy) <= 1) return 1;
if (!(abs(px - bx) <= 1 && abs(py - by) <= 1)) return 1;
return 0;
}
bool is_ok (board B) {
return mp.find(B.get_hash()) != mp.end();
}
void add_edge_if_ok (int node, board sus_state) {
if (!is_ok(sus_state)) return;
int sus = mp[sus_state.get_hash()];
v[node].push_back(sus);
r[sus].push_back(node);
}
void gen_graph () {
for (int wx = 0; wx <= 7; wx++) {
for (int wy = 0; wy <= 7; wy++) {
for (int bx = 0; bx <= 7; bx++) {
for (int by = 0; by <= 7; by++) {
for (int px = 0; px <= 7; px++) {
for (int py = 1; py <= 8; py++) {
for (int turn = 0; turn < 2; turn++) {
if (valid(wx, wy, bx, by, px, py, turn)) {
cnt++;
state[cnt] = {wx, wy, bx, by, px, py, turn};
mp[state[cnt].get_hash()] = cnt;
}
}
}
}
}
}
}
}
for (int node = 1; node <= cnt; node++) {
int wx = state[node].wx, wy = state[node].wy;
int bx = state[node].bx, by = state[node].by;
int px = state[node].px, py = state[node].py;
int turn = state[node].turn;
if (turn == 0) { // white
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i == 0 && j == 0) continue;
board sus_state(wx + i, wy + j, bx, by, px, py, !turn);
add_edge_if_ok(node, sus_state);
}
}
if (py <= 6) {
if (!(wx == px && wy == py + 1)) {
board sus_state(wx, wy, bx, by, px, py + 1, !turn);
add_edge_if_ok(node, sus_state);
if (py == 1 && !(wx == px && wy == py + 2)) {
board sus_state2(wx, wy, bx, by, px, py + 2, !turn);
add_edge_if_ok(node, sus_state2);
}
}
}
} else { // black
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i == 0 && j == 0) continue;
board sus_state(wx, wy, bx + i, by + j, px, ((bx + i == px && by + j == py) ? 9 : py ), !turn);
add_edge_if_ok(node, sus_state);
}
}
}
}
}
int prom[10000000];
void calc () {
for (int node = 1; node <= cnt; node++) {
int wx = state[node].wx, wy = state[node].wy;
int bx = state[node].bx, by = state[node].by;
int px = state[node].px, py = state[node].py;
int turn = state[node].turn;
deg[node] = v[node].size();
if (promotion_win(wx, wy, bx, by, px, py, turn)) {
sol[node] = 0; prom[node] = 1;
q.push(node);
} else if (deg[node] == 0) {
q.push(node);
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
if (sol[x] != -1 && !prom[x]) continue;
sol[x] = 0;
for (auto sus : v[x]) {
if (sol[sus] == 0) sol[x] = 1;
}
for (auto sus : r[x]) {
deg[sus]--;
if (deg[sus] == 0 || sol[x] == 0) q.push(sus);
}
}
}
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(sol, -1, sizeof sol);
gen_graph();
calc();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
string w, b, p, turn_s;
cin >> w >> p >> b >> turn_s;
int wx = w[0] - 'a', wy = w[1] - '1';
int bx = b[0] - 'a', by = b[1] - '1';
int px = p[0] - 'a', py = p[1] - '1';
int turn = (turn_s == "w" ? 0 : 1);
board ploca(wx, wy, bx, by, px, py, turn);
int node = mp[ploca.get_hash()];
// cout << "sol je " << sol[node] << endl;
// cout << "deg je " << deg[node] << endl;
if (sol[node] == 1) cout << "Win\n"; else cout << "Draw\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 980ms
memory: 186664kb
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:
Win Draw Win Win Draw Draw
result:
wrong answer 1st lines differ - expected: 'Draw', found: 'Win'