QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230017#7635. Fairy Chessucup-team1883#AC ✓679ms3692kbC++142.8kb2023-10-28 17:25:272023-10-28 17:25:28

Judging History

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

  • [2023-10-28 17:25:28]
  • 评测
  • 测评结果:AC
  • 用时:679ms
  • 内存:3692kb
  • [2023-10-28 17:25:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 15;
const ull M = ULLONG_MAX;
char s[N];
void print(ull x) {
  
  for(int i = 0; i < 8; i++, puts("")) {
    for(int j = 0; j < 8; j++) printf("%d ", x >> (8 * i | j) & 1);
  }
  puts("=====");
}
ull Diag(int i, int j, ull B) {
  int x = i, y = j;
  ull res = 1ull << (x * 8 | y);
  while(x > 0 && y > 0) {
    x--; y--;
    res |= 1ull << (x * 8 | y);
  }
  x = i; y = j;
  while(x < 7 && y < 7) {
    x++; y++;
    res |= 1ull << (x * 8 | y);
  }
  x = i; y = j;
  while(x < 7 && y > 0) {
    x++; y--;
    res |= 1ull << (x * 8 | y);
  }
  x = i; y = j;
  while(x > 0 && y < 7) {
    x--; y++;
    res |= 1ull << (x * 8 | y);
  }
  if(B & res) return M;
  return res;
}
ull Line(int i, int j, ull B) {
  ull res = 0;
  for(int x = 0; x < 8; x++) {
    res |= 1ull << (x * 8 | j);
  }
  for(int y = 0; y < 8; y++) {
    res |= 1ull << (i * 8 | y);
  }
  if(B & res) return M;
  return res;
}
ull Ri(int i, int j, ull B) {
  static int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
  static int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
  ull res = 0;
  for(int d = 0; d < 8; d++) {
    int x = i + dx[d], y = j + dy[d];
    if(x < 0 || x > 7 || y < 0 || y > 7) continue;
    res |= 1ull << (x * 8 | y);
  }
  if(B & res) return M;
  return res;
}
bool dfs(int k, ull A, ull B) {
  // printf("(%llu %llu) %d\n", A, B, k);
  // system("pause");
  char cur = s[k];
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      if(A >> (i * 8 | j) & 1) continue;
      // bool pr = false;
      // if(s[k] == 'R' && i == 6 && j == 0) pr = true;
      ull s1 = 0, s2 = 0, s3 = 0;
      // if(k == 2) printf("(%d %d)\n", i, j);
      if(cur == 'B' || cur == 'Q' || cur == 'A' || cur == 'M') {
        s1 = Diag(i, j, B);
      }
      if(cur == 'R' || cur == 'Q' || cur == 'C' || cur == 'M') {
        s2 = Line(i, j, B);
      }
      if(cur == 'A' || cur == 'C' || cur == 'M') {
        s3 = Ri(i, j, B);
      }
      // if(pr) printf("%llu %llu %llu\n", s1, s2, s3);
      if(s1 < M && s2 < M && s3 < M) {
        if(!dfs(k + 1, A | s1 | s2 | s3, (1ull << (i * 8 | j)) | B)) {
          return true;
        }
      }
    }
  }
  // if(s[k] == 'R') {
  //   printf("%c\n", s[k]);
  //   for(int i = 0; i < 8; i++, puts("")) {
  //     for(int j = 0; j < 8; j++) printf("%d ", A >> (8 * i | j) & 1);
  //   }
  //   puts("");
  //   for(int i = 0; i < 8; i++, puts("")) {
  //     for(int j = 0; j < 8; j++) printf("%d ", B >> (8 * i | j) & 1);
  //   }
  //   system("pause");
  // }
  return false;
}
int main() {
  cin >> s;

  if(dfs(0, 0ull, 0ull)) {
    puts("Alice");
  } else {
    puts("Bob");
  }
  // print(Diag(0, 0, 0));
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 63ms
memory: 3528kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 33ms
memory: 3632kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 22ms
memory: 3600kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 47ms
memory: 3532kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 23ms
memory: 3532kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 22ms
memory: 3556kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 82ms
memory: 3636kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 397ms
memory: 3684kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 103ms
memory: 3596kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 234ms
memory: 3492kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 229ms
memory: 3528kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 679ms
memory: 3600kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

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

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed