QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#165374 | #7180. Forward-Capturing Pawns | ucup-team004# | AC ✓ | 1070ms | 194000kb | C++20 | 11.2kb | 2023-09-05 17:46:56 | 2023-09-05 17:46:56 |
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) && y == 1) {
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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 973ms
memory: 189852kb
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: 1070ms
memory: 194000kb
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