QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#173727#7180. Forward-Capturing Pawnsucup-team180#AC ✓347ms84964kbC++178.1kb2023-09-10 01:29:102023-09-10 01:29:10

Judging History

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

  • [2023-09-10 01:29:10]
  • 评测
  • 测评结果:AC
  • 用时:347ms
  • 内存:84964kb
  • [2023-09-10 01:29:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
vector<int> dx = {1, 0, -1, 0, 1, 1, -1, -1};
vector<int> dy = {0, 1, 0, -1, 1, -1, 1, -1};
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  auto X = [&](int x){
    return x & 7;
  };
  auto Y = [&](int x){
    return x >> 3 & 7;
  };
  auto wk = [&](int x){
    return x & 63;
  };
  auto wp = [&](int x){
    return x >> 6 & 63;
  };
  auto bk = [&](int x){
    return x >> 12 & 63;
  };
  auto in_grid = [&](int x, int y){
    return 0 <= x && x < 8 && 0 <= y && y < 8;
  };
  auto piece = [&](int x, int y){
    return x | (y << 3);
  };
  auto board = [&](int WK, int WP, int BK){
    return WK | (WP << 6) | (BK << 12);
  };
  vector<bool> is_distinct(1 << 18, true);
  for (int i = 0; i < (1 << 18); i++){
    if (wk(i) == bk(i) || bk(i) == wp(i) || wp(i) == wk(i)){
      is_distinct[i] = false;
    }
  }
  vector<bool> king_check(1 << 18, false);
  for (int i = 0; i < (1 << 18); i++){
    if (abs(X(wk(i)) - X(bk(i))) <= 1 && abs(Y(wk(i)) - Y(bk(i))) <= 1){
      king_check[i] = true;
    }
  }
  vector<vector<bool>> piece_check(2, vector<bool>(1 << 18, false));
  for (int i = 0; i < (1 << 18); i++){
    if (X(bk(i)) == X(wp(i))){
      if (Y(bk(i)) == Y(wp(i)) + 1){
        piece_check[0][i] = true;
      }
      if (Y(wp(i)) == 1 && Y(bk(i)) == 3){
        if (!(X(wk(i)) == X(wp(i)) && Y(wk(i)) == Y(wp(i)) + 1)){
          piece_check[0][i] = true;
        }
      }
    }
  }
  for (int i = 0; i < (1 << 18); i++){
    for (int j = 0; j < 8; j++){
      int x = X(wp(i)), y = Y(wp(i));
      while (true){
        x += dx[j];
        y += dy[j];
        if (!in_grid(x, y)){
          break;
        }
        if (piece(x, y) == wk(i)){
          break;
        }
        if (piece(x, y) == bk(i)){
          piece_check[1][i] = true;
        }
      }
    }
  }
  vector<vector<bool>> is_checkmate(2, vector<bool>(1 << 18, false));
  vector<vector<bool>> is_stalemate(2, vector<bool>(1 << 18, false));
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < (1 << 18); j++){
      if (is_distinct[j] && !king_check[j]){
        bool ok = true;
        for (int k = 0; k < 8; k++){
          int x = X(bk(j)) + dx[k];
          int y = Y(bk(j)) + dy[k];
          if (in_grid(x, y)){
            int j2 = board(wk(j), wp(j), piece(x, y));
            if (is_distinct[j2]){
              if (!king_check[j2] && !piece_check[i][j2]){
                ok = false;
              }
            }
            if (wp(j) == piece(x, y) && !king_check[j2]){
              ok = false;
            }
          }
        }
        if (ok){
          if (piece_check[i][j]){
            is_checkmate[i][j] = true;
          } else {
            is_stalemate[i][j] = true;
          }
        }
      }
    }
  }
  vector<vector<vector<bool>>> is_reasonable(2, vector<vector<bool>>(2, vector<bool>(1 << 18, true)));
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < 2; j++){
      for (int k = 0; k < (1 << 18); k++){
        if (!is_distinct[k]){
          is_reasonable[i][j][k] = false;
        }
        if (j == 0 && (Y(wp(k)) == 0 || Y(wp(k)) == 7)){
          is_reasonable[i][j][k] = false;
        }
        if (king_check[k]){
          is_reasonable[i][j][k] = false;
        }
        if (i == 0 && piece_check[j][k]){
          is_reasonable[i][j][k] = false;
        }
      }
    }
  }
  vector<vector<bool>> can_capture(2, vector<bool>(1 << 18, false));
  vector<vector<vector<vector<int>>>> E(2, vector<vector<vector<int>>>(2, vector<vector<int>>(1 << 18)));
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < 2; j++){
      for (int k = 0; k < (1 << 18); k++){
        int id = (j << 18) | k;
        if (is_reasonable[i][j][k]){
          if (i == 0){
            for (int l = 0; l < 8; l++){
              int x = X(wk(k)) + dx[l];
              int y = Y(wk(k)) + dy[l];
              if (in_grid(x, y)){
                int k2 = board(piece(x, y), wp(k), bk(k));
                if (is_reasonable[1][j][k2]){
                  E[1][j][k2].push_back(id);
                }
              }
            }
          }
          if (i == 0 && j == 0){
            int y = Y(wp(k));
            for (int y2 = y + 1; y2 <= min(6, max(y + 1, 3)); y2++){
              int k2 = board(wk(k), piece(X(wp(k)), y2), bk(k));
              if (is_reasonable[1][0][k2]){
                E[1][0][k2].push_back(id);
              }
            }
            if (y == 6){
              int k2 = board(wk(k), piece(X(wp(k)), 7), bk(k));
              if (is_reasonable[1][1][k2]){
                E[1][1][k2].push_back(id);
              }
            }
          }
          if (i == 0 && j == 1){
            for (int l = 0; l < 8; l++){
              int x = X(wp(k));
              int y = Y(wp(k));
              while (true){
                x += dx[l];
                y += dy[l];
                if (!in_grid(x, y)){
                  break;
                }
                if (piece(x, y) == wk(k) || piece(x, y) == bk(k)){
                  break;
                }
                int k2 = board(wk(k), piece(x, y), bk(k));
                if (is_reasonable[1][1][k2]){
                  E[1][1][k2].push_back(id);
                }
              }
            }
          }
          if (i == 1){
            for (int l = 0; l < 8; l++){
              int x = X(bk(k)) + dx[l];
              int y = Y(bk(k)) + dy[l];
              if (in_grid(x, y)){
                int k2 = board(wk(k), wp(k), piece(x, y));
                if (is_reasonable[0][j][k2]){
                  E[0][j][k2].push_back(id);
                }
                if (wp(k) == piece(x, y) && !king_check[k2]){
                  can_capture[j][k] = true;
                }
              }
            }
          }
        }
      }
    }
  }
  vector<vector<vector<int>>> deg(2, vector<vector<int>>(2, vector<int>(1 << 18, 0)));
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < 2; j++){
      for (int k = 0; k < (1 << 18); k++){
        for (int l : E[i][j][k]){
          deg[i ^ 1][l >> 18][l & ((1 << 18) - 1)]++;
        }
      }
    }
  }
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < (1 << 18); j++){
      if (can_capture[i][j]){
        deg[1][i][j]++;
      }
    }
  }
  vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(2, vector<bool>(1 << 18, false)));
  queue<tuple<int, int, int>> Q;
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < (1 << 18); j++){
      if (is_checkmate[i][j]){
        dp[1][i][j] = true;
        Q.push(make_tuple(1, i, j));
      }
    }
  }
  vector<int> corner;
  corner.push_back(board(piece(0, 4), piece(2, 6), piece(0, 6)));
  corner.push_back(board(piece(7, 4), piece(5, 6), piece(7, 6)));
  corner.push_back(board(piece(0, 3), piece(1, 6), piece(0, 5)));
  corner.push_back(board(piece(1, 3), piece(1, 6), piece(0, 5)));
  corner.push_back(board(piece(7, 3), piece(6, 6), piece(7, 5)));
  corner.push_back(board(piece(6, 3), piece(6, 6), piece(7, 5)));
  for (int x : corner){
    dp[0][0][x] = true;
    Q.push(make_tuple(0, 0, x));
  }
  while (!Q.empty()){
    int t = get<0>(Q.front());
    int p = get<1>(Q.front());
    int b = get<2>(Q.front());
    Q.pop();
    for (int x : E[t][p][b]){
      int p2 = x >> 18;
      int b2 = x & ((1 << 18) - 1);
      if (t == 0 && is_stalemate[p2][b2]){
        continue;
      }
      if (t == 0){
        deg[1][p2][b2]--;
        if (deg[1][p2][b2] == 0){
          dp[1][p2][b2] = true;
          Q.push(make_tuple(1, p2, b2));
        }
      }
      if (t == 1 && !dp[0][p2][b2]){
        dp[0][p2][b2] = true;
        Q.push(make_tuple(0, p2, b2));
      }
    }
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    string WK, WP, BK, T;
    cin >> WK >> WP >> BK >> T;
    int turn = (T == "w" ? 0 : 1);
    int b = board(piece(WK[0] - 'a', WK[1] - '1'), piece(WP[0] - 'a', WP[1] - '1'), piece(BK[0] - 'a', BK[1] - '1'));
    if (dp[turn][0][b]){
      cout << "Win" << '\n';
    } else {
      cout << "Draw" << '\n';
    }
  }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 303ms
memory: 84964kb

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: 347ms
memory: 84672kb

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