QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#174657#7180. Forward-Capturing Pawnshos_lyricAC ✓170ms58724kbC++148.5kb2023-09-10 11:54:012023-09-10 11:54:01

Judging History

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

  • [2023-09-10 11:54:01]
  • 评测
  • 测评结果:AC
  • 用时:170ms
  • 内存:58724kb
  • [2023-09-10 11:54:01]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int lens[64];
int adj[64][8];

// White king, White pawn, Black king
int V;
int ids[64][64][64][2];
vector<int> turnOf;
vector<vector<int>> graph, hparg;

bool adjacent(int a, int b) {
  const int ax = a / 8, ay = a % 8;
  const int bx = b / 8, by = b % 8;
  return (abs(ax - bx) <= 1 && abs(ay - by) <= 1);
}
bool checkedA(int a, int /*b*/, int c) {
  if (adjacent(a, c)) return true;
  return false;
}
bool checkedC(int a, int b, int c) {
  const int ax = a / 8, ay = a % 8;
  const int bx = b / 8, by = b % 8;
  const int cx = c / 8, cy = c % 8;
  if (adjacent(a, c)) return true;
  if (by == cy) {
    if (bx - 1 == cx) return true;
    if (bx == 6 && cx == 4 && make_pair(ax, ay) != make_pair(5, by)) return true;
  }
  return false;
}
bool isReasonable(int a, int b, int c, int t) {
  // const int ax = a / 8, ay = a % 8;
  const int bx = b / 8/*, by = b % 8*/;
  // const int cx = c / 8, cy = c % 8;
  // 1
  if (a == b) return false;
  if (a == c) return false;
  if (b == c) return false;
  // 2
  if (bx == 0 || bx == 7) return false;
  // 3
  if (t == 0) {
    if (checkedC(a, b, c)) return false;
  } else {
    if (checkedA(a, b, c)) return false;
  }
  return true;
}

bool checkedCRook(int a, int b, int c) {
  const int ax = a / 8, ay = a % 8;
  const int bx = b / 8, by = b % 8;
  const int cx = c / 8, cy = c % 8;
  if (adjacent(a, c)) return true;
  if (bx == cx && !(ax == bx && (ay - by) * (ay - cy) < 0)) return true;
  if (by == cy && !(ay == by && (ax - bx) * (ax - cx) < 0)) return true;
  return false;
}
bool rookStalemate(int a, int b, int c) {
  // check
  if (checkedCRook(a, b, c)) return false;
  // mate
  for (int h = 0; h < lens[c]; ++h) {
    const int cc = adj[c][h];
    assert(a != cc);
    if (b == cc) {
      if (!adjacent(a, cc)) return false;
    } else {
      if (!checkedCRook(a, b, cc)) return false;
    }
  }
cerr<<"rookStalemate "<<make_pair(a/8,a%8)<<" "<<make_pair(b/8,b%8)<<" "<<make_pair(c/8,c%8)<<endl;
// return false;//?
  return true;
}

int readPiece() {
  char buf[10];
  scanf("%s", buf);
  const int x = '8' - buf[1];
  const int y = buf[0] - 'a';
  assert(0 <= x); assert(x < 8);
  assert(0 <= y); assert(y < 8);
  return x * 8 + y;
}
int readTurn() {
  char c;
  scanf(" %c", &c);
  return (c == 'b') ? 1 : 0;
}
int main() {
  memset(adj, ~0, sizeof(adj));
  for (int a = 0; a < 64; ++a) {
    const int x = a / 8, y = a % 8;
    for (int dx = -1; dx <= +1; ++dx) for (int dy = -1; dy <= +1; ++dy) if (dx || dy) {
      const int xx = x + dx;
      const int yy = y + dy;
      if (0 <= xx && xx < 8 && 0 <= yy && yy < 8) {
        const int b = xx * 8 + yy;
        adj[a][lens[a]++] = b;
      }
    }
// pv(adj[a],adj[a]+lens[a]);
  }
  
  V = 2;
  memset(ids, ~0, sizeof(ids));
  turnOf = {1, 1};
  for (int a = 0; a < 64; ++a) for (int b = 0; b < 64; ++b) for (int c = 0; c < 64; ++c) {
    for (int t = 0; t < 2; ++t) {
      if (isReasonable(a, b, c, t)) {
        ids[a][b][c][t] = V++;
        turnOf.push_back(t);
      }
    }
  }
cerr<<"V = "<<V<<endl;
  graph.assign(V, {});
  graph[1].push_back(1);
  for (int a = 0; a < 64; ++a) for (int b = 0; b < 64; ++b) for (int c = 0; c < 64; ++c) {
    const int ax = a / 8, ay = a % 8;
    const int bx = b / 8, by = b % 8;
    const int cx = c / 8, cy = c % 8;
    for (int t = 0; t < 2; ++t) {
      const int u = ids[a][b][c][t];
      if (~u) {
        if (t == 0) {
          // king
          for (int h = 0; h < lens[a]; ++h) {
            const int aa = adj[a][h];
            const int v = ids[aa][b][c][t ^ 1];
            if (~v) {
// if(u==90324)cerr<<make_pair(aa/8,aa%8)<<" "<<v<<endl;
              graph[u].push_back(v);
            }
          }
          // pawn
          for (int bbx = bx - 1; bbx >= ((bx == 6) ? 4 : (bx - 1)); --bbx) {
            const int bby = by;
// cerr<<"pawn "<<make_pair(ax,ay)<<" "<<make_pair(bx,by)<<"->"<<make_pair(bbx,bby)<<" "<<make_pair(cx,cy)<<endl;
            if (bx == 6 && bbx == 4 && (make_pair(ax, ay) == make_pair(5, by) || make_pair(cx, cy) == make_pair(5, by))) {
              // jump
// cerr<<"jump "<<make_pair(ax,ay)<<" "<<make_pair(bx,by)<<"->"<<make_pair(bbx,bby)<<" "<<make_pair(cx,cy)<<endl;
              continue;
            }
            const int bb = bbx * 8 + bby;
            const int v = ids[a][bb][c][t ^ 1];
            if (~v) {
              graph[u].push_back(v);
            } else if (a != bb && bbx == 0) {
              // promotion
// if(u==54374||u==54376||u==54386||u==54394||u==54396)cerr<<__LINE__<<" promo "<<u<<" "<<make_pair(bbx,bby)<<endl;
              if (adjacent(bb, c)) {
                if (adjacent(bb, a)) {
                  if (!rookStalemate(a, bb, c)) graph[u].push_back(0);
                } else {
                  // useless
                }
              } else {
                if (!rookStalemate(a, bb, c)) graph[u].push_back(0);
              }
            }
          }
        } else {
          // king
          for (int h = 0; h < lens[c]; ++h) {
            const int cc = adj[c][h];
            const int v = ids[a][b][cc][t ^ 1];
            if (~v) {
              graph[u].push_back(v);
            } else if (cc == b) {
              // capture
              if (adjacent(cc, a)) {
                // invalid
              } else {
                graph[u].push_back(1);
              }
            }
          }
          if (graph[u].empty()) {
            // checkmate or stalemate
            if (!checkedC(a, b, c)) {
cerr<<"stalemate "<<make_pair(ax,ay)<<" "<<make_pair(bx,by)<<" "<<make_pair(cx,cy)<<endl;
              graph[u].push_back(1);
            }
          }
        }
if(u==89138)cerr<<__LINE__<<" "<<graph[u]<<endl;
      }
    }
  }
  
  vector<int> deg(V);
  hparg.assign(V, {});
  for (int u = 0; u < V; ++u) {
    deg[u] = graph[u].size();
    for (const int v : graph[u]) {
      hparg[v].push_back(u);
    }
  }
  vector<int> ans(V, 0);
  queue<int> que;
  for (int u = 0; u < V; ++u) if (turnOf[u] == 1 && deg[u] == 0) {
    que.push(u);
  }
  for (; !que.empty(); ) {
    // v: Win
    const int v = que.front();
    que.pop();
    assert(!ans[v]);
    ans[v] = 1;
    for (const int u : hparg[v]) {
      if (turnOf[u] == 0) {
        if (deg[u]) {
          que.push(u);
        }
        deg[u] = 0;
      } else {
        if (--deg[u] == 0) {
          que.push(u);
        }
      }
    }
  }
int sumAns=0;for(int u=0;u<V;++u)sumAns+=ans[u];cerr<<"sumAns = "<<sumAns<<endl;
  for (int u = 0; u < V; ++u) {
    if (turnOf[u] == 0) {
      int win = 0;
      for (const int v : graph[u]) if (ans[v]) win = 1;
      assert(ans[u] == win);
    } else {
      int win = 1;
      for (const int v : graph[u]) if (!ans[v]) win = 0;
      assert(ans[u] == win);
    }
  }
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    const int a = readPiece();
    const int b = readPiece();
    const int c = readPiece();
    const int t = readTurn();
    
    assert(isReasonable(a, b, c, t));
    const int u = ids[a][b][c][t];
// cerr<<a<<" "<<b<<" "<<c<<" "<<t<<": "<<u<<" "<<ids[a][b][c][t^1]<<endl;
    assert(~u);
    puts(ans[u] ? "Win" : "Draw");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 102ms
memory: 58724kb

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: 170ms
memory: 58608kb

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