QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#166528 | #7180. Forward-Capturing Pawns | ucup-team1209# | AC ✓ | 221ms | 104544kb | C++20 | 4.1kb | 2023-09-06 14:20:21 | 2023-09-06 14:20:21 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
struct point {
int a, b, c, o;
};
vector <point> mp[1 << 20];
int win[1 << 20];
int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int ID(point x) {
return x.o * 64 * 64 * 64 + x.a * 64 * 64 + x.b * 64 + x.c;
}
int id(int x, int y) {
return x * 8 + y;
}
bool near(int x, int y, int p) {
int px = p / 8, py = p % 8;
for(int e = 0; e < 8; e++)
if(x + dx[e] == px && y + dy[e] == py) return true;
return false;
}
bool pawn(int x, int y, int p) {
int px = p / 8, py = p % 8;
if(px + 1 == x && py == y) return true;
if(px == 1 && px + 2 == x && py == y) return true;
return false;
}
bool in(int x, int y) {
return 0 <= x && x < 8 && 0 <= y && y < 8;
}
int pos(char *a) {
int i = a[0] - 'a';
int j = a[1] - '1';
return id(j, i);
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
for(int i = 0; i < 64; i++)
for(int j = 0; j < 64; j++)
for(int k = 0; k < 64; k++)
for(int o = 0; o < 2; o++) {
if(o == 0) { // w
int px = j / 8, py = j % 8;
if(px == 7) {
win[ID({i, j, k, o})] = 1;
continue;
}
if(id(px + 1, py) != i) {
mp[ID({i, j, k, o})].pb({i, id(px + 1, py), k, o ^ 1});
}
if(px == 1 && id(px + 1, py) != i && id(px + 2, py) != i) {
mp[ID({i, j, k, o})].pb({i, id(px + 2, py), k, o ^ 1});
}
int kx = i / 8, ky = i % 8;
for(int e = 0; e < 8; e++) {
int nx = kx + dx[e];
int ny = ky + dy[e];
if(in(nx, ny) && !near(nx, ny, k) && id(nx, ny) != j) {
mp[ID({i, j, k, o})].pb({id(nx, ny), j, k, o ^ 1});
}
}
}
if(o == 1) {
int kx = k / 8, ky = k % 8;
bool hav = 0;
for(int e = 0; e < 8; e++) {
int nx = kx + dx[e];
int ny = ky + dy[e];
if(in(nx, ny) && !near(nx, ny, i) && !pawn(nx, ny, j)) {
if(id(nx, ny) == j) {
win[ID({i, j, k, o})] = -1;
}
hav = 1;
mp[ID({i, j, k, o})].pb({i, j, id(nx, ny), o ^ 1});
}
}
if(!hav) {
win[ID({i, j, k, o})] = -1;
}
}
}
for(int t = 0; t < 50; t++) {
for(int i = 0; i < 64; i++)
for(int j = 0; j < 64; j++)
for(int k = 0; k < 64; k++)
for(int o = 0; o < 2; o++) {
int u = ID({i, j, k, o});
if(win[u] == 0) {
if(o == 0) {
bool lose = 1;
for(auto v : mp[u]) {
int wi = win[ID(v)];
if(wi == 1) win[u] = 1;
if(wi != -1) lose = 0;
}
if(lose) {
win[u] = -1;
}
}
if(o == 1) {
bool lose = 1;
for(auto v : mp[u]) {
int wi = win[ID(v)];
if(wi == -1) win[u] = -1;
if(wi != 1) lose = 0;
}
if(lose) {
win[u] = 1;
}
}
}
}
}
int T = 0;
cin >> T;
while(T--) {
char a[5], b[5], c[5], e[5];
scanf("%s%s%s%s", a, b, c, e);
int i = pos(a), j = pos(b), k = pos(c), o = e[0] == 'b';
// cout << i << ' ' << j << ' ' << k << endl;
int ans = win[ID({i, j, k, o})];
if(ans == 1) {
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: 206ms
memory: 104476kb
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: 221ms
memory: 104544kb
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