QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#451502#7635. Fairy ChessCelestialCoder#WA 50ms3660kbC++172.2kb2024-06-23 15:22:112024-06-23 15:22:11

Judging History

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

  • [2024-06-23 15:22:11]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:3660kb
  • [2024-06-23 15:22:11]
  • 提交

answer

#include <cassert>
#include <iostream>
using namespace std;

string str;

typedef unsigned long long mask;

mask bishop[64];
mask rook[64];
mask knight[64];
int ndx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int ndy[] = {2, 1, -1, -2, -2, -1, 1, 2};

int bdx[] = {1, 1, -1, -1};
int bdy[] = {1, -1, 1, -1};

int rdx[] = {1, 0, -1, 0};
int rdy[] = {0, 1, 0, -1};

int valid(int x, int y) {
  return x >= 0 && x < 8 && y >= 0 && y < 8;
}

mask compute_next_mask(mask attacks, char ty, int pos) {
  mask next = attacks;
  if (ty == 'B')
    next |= bishop[pos];
  else if (ty == 'A')
    next |= bishop[pos] | knight[pos];
  else if (ty == 'R')
    next |= rook[pos];
  else if (ty == 'Q')
    next |= bishop[pos] | rook[pos];
  else if (ty == 'C')
    next |= rook[pos] | knight[pos];
  else
    next |= rook[pos] | bishop[pos] | knight[pos];
  return next;
}

int dfs(mask current, mask attacks, int idx) {
  if (idx > 12) {
    cout << "error" << endl;
  }
  for (int i = 0; i < 64; ++i) {
    if (attacks >> i & 1 || current >> i & 1) {
      continue;
    }

    mask next_attack = compute_next_mask(attacks, str[idx], i);
    if (current & next_attack)
      continue;

    mask next_current = current | 1ULL << i;
    if (!dfs(next_current, next_attack, idx + 1))
      return 1;
  }
  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> str;

  for (int i = 0; i < 64; ++i) {
    int x = i / 8;
    int y = i % 8;
    for (int j = 0; j < 8; ++j) {
      int nx = x + ndx[j];
      int ny = y + ndy[j];
      if (!valid(nx, ny))
        continue;
      knight[i] |= 1ULL << nx * 8 + y;
    }

    for (int j = 0; j < 4; ++j) {
      int cx = x, cy = y;
      cx += rdx[j], cy += rdy[j];
      while (valid(cx, cy)) {
        rook[i] |= 1ULL << cx * 8 + cy;
        cx += rdx[j], cy += rdy[j];
      }
    }

    for (int j = 0; j < 4; ++j) {
      int cx = x, cy = y;
      cx += bdx[j], cy += bdy[j];
      while (valid(cx, cy)) {
        bishop[i] |= 1ULL << cx * 8 + cy;
        cx += bdx[j], cy += bdy[j];
      }
    }
  }

  if (dfs(0, 0, 0)) {
    cout << "Alice";
  } else {
    cout << "Bob";
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 50ms
memory: 3656kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 5ms
memory: 3660kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: -100
Wrong Answer
time: 14ms
memory: 3660kb

input:

QQRAACMRMCBB

output:

Bob

result:

wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'