QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166528#7180. Forward-Capturing Pawnsucup-team1209#AC ✓221ms104544kbC++204.1kb2023-09-06 14:20:212023-09-06 14:20:21

Judging History

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

  • [2023-09-06 14:20:21]
  • 评测
  • 测评结果:AC
  • 用时:221ms
  • 内存:104544kb
  • [2023-09-06 14:20:21]
  • 提交

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