QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#165363 | #7180. Forward-Capturing Pawns | ucup-team004# | WA | 1125ms | 193804kb | C++20 | 11.2kb | 2023-09-05 17:44:20 | 2023-09-05 17:44:20 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
int win[65][64][64][5][2] {};
int h[65][64][64][5][2] {};
int deg[65][64][64][5][2] {};
bool r[65][64][64][5][2] {};
int edges;
int to[20000000];
int nxt[20000000];
int pack(int a, int b, int c, int d, int e) {
return (((a * 64 + b) * 64 + c) * 5 + d) * 2 + e;
}
void add(int a1, int b1, int c1, int d1, int e1,
int a2, int b2, int c2, int d2, int e2) {
// if (a2 == 30 && b2 == 1 && c2 == 38 && d2 == 0 && e2 == 0) {
// std::cerr << a1 << " " << b1 << " " << c1 << " " << d1 << " " << e1 << "\n";
// }
int v = pack(a2, b2, c2, d2, e2);
deg[a2][b2][c2][d2][e2]++;
int &H = h[a1][b1][c1][d1][e1];
++edges;
to[edges] = v;
nxt[edges] = H;
H = edges;
}
std::array<int, 5> unpack(int s) {
return {s / (64 * 64 * 5 * 2), s / (64 * 5 * 2) % 64, s / (5 * 2) % 64, s / 2 % 5, s % 2};
}
bool legal(int x, int y) {
return 0 <= x && x < 8 && 0 <= y && y < 8;
}
bool contains(i64 a, int b) {
return a >> b & 1;
}
i64 moves(int a, int t, int u, int v1, int v2) {
i64 ans = 0;
const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
if (t == 0) {
int x = a / 8, y = a % 8;
if (legal(x, y + 1)) {
int b = x * 8 + (y + 1);
if (u != b) {
ans |= 1LL << b;
if (v1 != b && v2 != b && legal(x, y + 2)) {
int c = x * 8 + (y + 2);
if (u != c) {
ans |= 1LL << c;
}
}
}
}
} else if (t == 1) {
for (int k = 0; k < 8; k++) {
int x = a / 8, y = a % 8;
while (true) {
x += dx[k];
y += dy[k];
if (!legal(x, y)) {
break;
}
int b = x * 8 + y;
if (u == b) {
break;
}
ans |= 1LL << b;
if (v1 == b || v2 == b) {
break;
}
}
}
} else if (t == 2) {
for (int k = 0; k < 8; k += 2) {
int x = a / 8, y = a % 8;
while (true) {
x += dx[k];
y += dy[k];
if (!legal(x, y)) {
break;
}
int b = x * 8 + y;
if (u == b) {
break;
}
ans |= 1LL << b;
if (v1 == b || v2 == b) {
break;
}
}
}
} else if (t == 3) {
for (int k = 1; k < 8; k += 2) {
int x = a / 8, y = a % 8;
while (true) {
x += dx[k];
y += dy[k];
if (!legal(x, y)) {
break;
}
int b = x * 8 + y;
if (u == b) {
break;
}
ans |= 1LL << b;
if (v1 == b || v2 == b) {
break;
}
}
}
} else if (t == 4) {
const int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
for (int k = 0; k < 8; k++) {
int x = a / 8, y = a % 8;
while (true) {
x += dx[k];
y += dy[k];
if (!legal(x, y)) {
break;
}
int b = x * 8 + y;
if (u == b) {
break;
}
ans |= 1LL << b;
break;
}
}
} else {
for (int k = 0; k < 8; k++) {
int x = a / 8, y = a % 8;
while (true) {
x += dx[k];
y += dy[k];
if (!legal(x, y)) {
break;
}
int b = x * 8 + y;
if (u == b) {
break;
}
ans |= 1LL << b;
break;
}
}
}
return ans;
}
int read() {
std::string s;
std::cin >> s;
return (s[0] - 'a') * 8 + (s[1] - '1');
}
bool check(int a, int b, int c, int d, int e) {
if (e == 0) {
if (a < 64 && contains(moves(a, d, b, c, -1), c)) {
return true;
}
if (contains(moves(b, 5, a, c, -1), c)) {
return true;
}
} else {
if (contains(moves(c, 5, -1, a, b), b)) {
return true;
}
}
return false;
}
bool reasonable(int a, int b, int c, int d, int e) {
if (a == b || b == c || c == a) {
return false;
}
if (a == 64 && d != 0) {
return false;
}
if (a < 64 && d == 0 && (a % 8 == 0 || a % 8 == 7)) {
return false;
}
if (check(a, b, c, d, e)) {
return false;
}
return true;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tot = 0;
for (int a = 0; a < 65; a++) {
for (int b = 0; b < 64; b++) {
for (int c = 0; c < 64; c++) {
for (int d = 0; d < 5; d++) {
for (int e = 0; e < 2; e++) {
if (reasonable(a, b, c, d, e)) {
r[a][b][c][d][e] = true;
tot++;
}
}
}
}
}
}
// std::cerr << tot << "\n";
tot = 0;
for (int a = 0; a < 65; a++) {
for (int b = 0; b < 64; b++) {
for (int c = 0; c < 64; c++) {
for (int d = 0; d < 5; d++) {
for (int e = 0; e < 2; e++) {
if (r[a][b][c][d][e]) {
if (e == 0) {
if (a < 64) {
i64 res = moves(a, d, b, c, -1);
for (int v = 0; v < 64; v++) {
if (contains(res, v)) {
if (v % 8 != 7 || d != 0) {
if (r[v][b][c][d][!e]) {
add(v, b, c, d, !e, a, b, c, d, e);
tot++;
}
} else {
for (int t = 1; t < 5; t++) {
if (r[v][b][c][t][!e]) {
add(v, b, c, t, !e, a, b, c, d, e);
tot++;
}
}
}
}
}
}
i64 res = moves(b, 5, a, c, -1);
for (int v = 0; v < 64; v++) {
if (contains(res, v) && r[a][v][c][d][!e]) {
add(a, v, c, d, !e, a, b, c, d, e);
tot++;
}
}
} else {
i64 res = moves(c, 5, -1, a, b);
for (int v = 0; v < 64; v++) {
if (contains(res, v)) {
if (v == a) {
if (r[64][b][v][0][!e]) {
add(64, b, v, 0, !e, a, b, c, d, e);
tot++;
}
} else {
if (r[a][b][v][d][!e]) {
add(a, b, v, d, !e, a, b, c, d, e);
tot++;
}
}
}
}
}
}
}
}
}
}
}
// std::cerr << tot << "\n";
std::queue<int> q;
std::memset(win, -1, sizeof(win));
for (int a = 0; a < 65; a++) {
for (int b = 0; b < 64; b++) {
for (int c = 0; c < 64; c++) {
for (int d = 0; d < 5; d++) {
for (int e = 0; e < 2; e++) {
if (r[a][b][c][d][e] && !deg[a][b][c][d][e]) {
win[a][b][c][d][e] = check(a, b, c, d, !e);
q.push(pack(a, b, c, d, e));
}
}
}
}
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
auto [a, b, c, d, e] = unpack(u);
for (int i = h[a][b][c][d][e]; i; i = nxt[i]) {
int v = to[i];
auto [a1, b1, c1, d1, e1] = unpack(v);
if (win[a1][b1][c1][d1][e1] == -1) {
if (e1 == 0 && win[a][b][c][d][e] == 1) {
win[a1][b1][c1][d1][e1] = 1;
q.push(v);
} else if (e1 == 0 && --deg[a1][b1][c1][d1][e1] == 0) {
win[a1][b1][c1][d1][e1] = 0;
q.push(v);
} else if (e1 == 1 && win[a][b][c][d][e] == 0) {
win[a1][b1][c1][d1][e1] = 0;
q.push(v);
} else if (e1 == 1 && --deg[a1][b1][c1][d1][e1] == 0) {
win[a1][b1][c1][d1][e1] = 1;
q.push(v);
}
}
}
}
int t;
std::cin >> t;
for (int _ = 0; _ < t; _++) {
int b = read();
int a = read();
int c = read();
int d = 0;
std::string s;
std::cin >> s;
int e = s == "w" ? 0 : 1;
// std::cerr << a << " " << b << " " << c << " " << d << " " << e << "\n";
std::cout << (win[a][b][c][d][e] == 1 ? "Win" : "Draw") << "\n";
}
// std::cerr << win[30][1][38][1][1] << "\n";
// std::cerr << win[31][1][38][1][1] << "\n";
// std::cerr << win[31][1][38][2][1] << "\n";
// std::cerr << win[31][1][38][3][1] << "\n";
// std::cerr << win[31][1][38][4][1] << "\n";
// std::cerr << win[30][0][38][0][1] << "\n";
// std::cerr << win[30][2][38][0][1] << "\n";
// std::cerr << win[30][8][38][0][1] << "\n";
// std::cerr << win[30][9][38][0][1] << "\n";
// std::cerr << win[30][1][38][0][1] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1034ms
memory: 193780kb
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: 1125ms
memory: 193804kb
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:
wrong answer 55773rd lines differ - expected: 'Draw', found: 'Win'