QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#232002#7635. Fairy Chesshos_lyricAC ✓95ms3820kbC++142.9kb2023-10-29 18:53:412023-10-29 18:53:41

Judging History

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

  • [2023-10-29 18:53:41]
  • 评测
  • 测评结果:AC
  • 用时:95ms
  • 内存:3820kb
  • [2023-10-29 18:53:41]
  • 提交

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 <random>
#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")


using U = unsigned long long;
constexpr int K = 6;
constexpr int N = 8;
constexpr int V = N * N;
int id(int x, int y) {
  return x * N + y;
}
U MOVE[K][V];

int A[2 * K];
bool calc(int i, U put, U cov) {
  if (i == 2 * K) {
    return false;
  } else {
    for (U q = ~cov; q; q &= q - 1) {
      const int u = __builtin_ctzll(q);
      if (!(put & MOVE[A[i]][u])) {
        if (!calc(i + 1, put | 1ULL << u, cov | MOVE[A[i]][u])) {
          return true;
        }
      }
    }
    return false;
  }
}

int main() {
  // bishop
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) for (int xx = 0; xx < N; ++xx) for (int yy = 0; yy < N; ++yy) {
    if (x + y == xx + yy || x - y == xx - yy) MOVE[0][id(x, y)] |= 1ULL << id(xx, yy);
  }
  // rook
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) for (int xx = 0; xx < N; ++xx) for (int yy = 0; yy < N; ++yy) {
    if (x == xx || y == yy) MOVE[1][id(x, y)] |= 1ULL << id(xx, yy);
  }
  // queen
  for (int u = 0; u < V; ++u) {
    MOVE[2][u] = MOVE[0][u] | MOVE[1][u];
  }
  // knight
  for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) for (int xx = 0; xx < N; ++xx) for (int yy = 0; yy < N; ++yy) {
    if ((xx - x) * (xx - x) + (yy - y) * (yy - y) == 5) MOVE[3][id(x, y)] |= 1ULL << id(xx, yy);
  }
  for (int u = 0; u < V; ++u) {
    MOVE[4][u] = MOVE[3][u];
    MOVE[5][u] = MOVE[3][u];
    MOVE[3][u] |= MOVE[0][u];
    MOVE[4][u] |= MOVE[1][u];
    MOVE[5][u] |= MOVE[2][u];
  }
  
  char S[110];
  for (; ~scanf("%s", S); ) {
    for (int i = 0; i < 2 * K; ++i) {
      A[i] = string("BRQACM").find(S[i]);
    }
    const bool ans = calc(0, 0, 0);
    puts(ans ? "Alice" : "Bob");
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 3720kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

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

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

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

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

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

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

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

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

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

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 18ms
memory: 3564kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed