QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210976#7180. Forward-Capturing Pawnsucup-team191WA 980ms186664kbC++146.0kb2023-10-11 22:21:022023-10-11 22:21:02

Judging History

你现在查看的是最新测评结果

  • [2023-10-11 22:21:02]
  • 评测
  • 测评结果:WA
  • 用时:980ms
  • 内存:186664kb
  • [2023-10-11 22:21:02]
  • 提交

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'