QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#451505#7635. Fairy ChessCelestialCoder#AC ✓538ms3696kbC++172.1kb2024-06-23 15:29:032024-06-23 15:29:03

Judging History

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

  • [2024-06-23 15:29:03]
  • 评测
  • 测评结果:AC
  • 用时:538ms
  • 内存:3696kb
  • [2024-06-23 15:29:03]
  • 提交

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) {
  assert(idx < 12);

  for (int i = 0; i < 64; ++i) {
    if (current >> i & 1)
      continue;
    mask next_current = current | 1ULL << i;
    mask next_attack = compute_next_mask(attacks, str[idx], i);
    if (next_current & next_attack)
      continue;

    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 + ny;
    }

    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: 52ms
memory: 3500kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 4ms
memory: 3612kb

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 8ms
memory: 3692kb

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: 0
Accepted
time: 7ms
memory: 3548kb

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

score: 0
Accepted
time: 7ms
memory: 3584kb

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

score: 0
Accepted
time: 7ms
memory: 3576kb

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

score: 0
Accepted
time: 7ms
memory: 3576kb

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 20ms
memory: 3688kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 14ms
memory: 3616kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

score: 0
Accepted
time: 4ms
memory: 3604kb

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 15ms
memory: 3584kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 19ms
memory: 3548kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

score: 0
Accepted
time: 12ms
memory: 3680kb

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 42ms
memory: 3584kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 17ms
memory: 3580kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 14ms
memory: 3548kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

score: 0
Accepted
time: 7ms
memory: 3548kb

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

score: 0
Accepted
time: 9ms
memory: 3548kb

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

score: 0
Accepted
time: 3ms
memory: 3536kb

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 17ms
memory: 3588kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

score: 0
Accepted
time: 7ms
memory: 3580kb

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

score: 0
Accepted
time: 7ms
memory: 3568kb

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 9ms
memory: 3696kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

score: 0
Accepted
time: 7ms
memory: 3608kb

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

score: 0
Accepted
time: 6ms
memory: 3624kb

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 61ms
memory: 3664kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 316ms
memory: 3584kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 28ms
memory: 3584kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 73ms
memory: 3584kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 51ms
memory: 3620kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 166ms
memory: 3452kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 173ms
memory: 3628kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 538ms
memory: 3488kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 31ms
memory: 3640kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 94ms
memory: 3584kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed