QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230299#7635. Fairy Chessucup-team1191#AC ✓1224ms112448kbC++235.1kb2023-10-28 18:02:152023-10-28 18:02:16

Judging History

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

  • [2023-10-28 18:02:16]
  • 评测
  • 测评结果:AC
  • 用时:1224ms
  • 内存:112448kb
  • [2023-10-28 18:02:15]
  • 提交

answer

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

enum class Piece {
  BISHOP,
  ROOK,
  QUEEN,
  ARCHBISHOP,
  CHANCELLOR,
  MAHARAJAH,
  KNIGHT,
};

const int N = 8;
const int K = 6;

ull mask_cover[N][N][K + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  auto valid = [&](int x, int y) { return 0 <= x && x < N && 0 <= y && y < N; };

  auto add = [&](int i, int j, int x, int y, Piece k) {
    if (valid(x, y)) {
      mask_cover[i][j][(int)k] |= 1ULL << (x * N + y);
    }
  };

  { // knight
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        add(i, j, i, j, Piece::KNIGHT);
        add(i, j, i + 1, j + 2, Piece::KNIGHT);
        add(i, j, i + 1, j - 2, Piece::KNIGHT);
        add(i, j, i - 1, j + 2, Piece::KNIGHT);
        add(i, j, i - 1, j - 2, Piece::KNIGHT);
        add(i, j, i + 2, j + 1, Piece::KNIGHT);
        add(i, j, i + 2, j - 1, Piece::KNIGHT);
        add(i, j, i - 2, j + 1, Piece::KNIGHT);
        add(i, j, i - 2, j - 1, Piece::KNIGHT);
      }
    }
  }

  { // bishop
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        for (int t = 0; t < 3 * N; ++t) {
          add(i, j, i + t, j + t, Piece::BISHOP);
          add(i, j, i + t, j - t, Piece::BISHOP);
          add(i, j, i - t, j + t, Piece::BISHOP);
          add(i, j, i - t, j - t, Piece::BISHOP);
        }
      }
    }
  }

  { // rook
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        for (int t = 0; t < 3 * N; ++t) {
          add(i, j, i + t, j, Piece::ROOK);
          add(i, j, i - t, j, Piece::ROOK);
          add(i, j, i, j + t, Piece::ROOK);
          add(i, j, i, j - t, Piece::ROOK);
        }
      }
    }
  }

  { // queen
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::QUEEN] =
            mask_cover[i][j][(int)Piece::BISHOP] |
            mask_cover[i][j][(int)Piece::ROOK];
      }
    }
  }

  { // archibishop
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::ARCHBISHOP] =
            mask_cover[i][j][(int)Piece::BISHOP] |
            mask_cover[i][j][(int)Piece::KNIGHT];
      }
    }
  }

  { // chancellor
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::CHANCELLOR] =
            mask_cover[i][j][(int)Piece::ROOK] |
            mask_cover[i][j][(int)Piece::KNIGHT];
      }
    }
  }

  { // maharajah
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        mask_cover[i][j][(int)Piece::MAHARAJAH] =
            mask_cover[i][j][(int)Piece::QUEEN] |
            mask_cover[i][j][(int)Piece::KNIGHT];
      }
    }
  }

  vector<int> order(2 * K);
  for (int i = 0; i < 2 * K; ++i) {
    char c;
    cin >> c;
    if (c == 'B') {
      order[i] = (int)Piece::BISHOP;
    } else if (c == 'R') {
      order[i] = (int)Piece::ROOK;
    } else if (c == 'Q') {
      order[i] = (int)Piece::QUEEN;
    } else if (c == 'A') {
      order[i] = (int)Piece::ARCHBISHOP;
    } else if (c == 'C') {
      order[i] = (int)Piece::CHANCELLOR;
    } else if (c == 'M') {
      order[i] = (int)Piece::MAHARAJAH;
    } else {
      assert(false);
    }
  }

  /*for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      cout << ((mask_cover[3][3][(int)Piece::MAHARAJAH] >> (N * i + j)) & 1);
    }
    cout << '\n';
  }
  return 0;*/
  mt19937_64 rnd(123);

  ull mask_pieces = 0;
  ull mask_covered = 0;

  int ptr = 0;

  map<pair<ull, ull>, bool> mem;
  function<bool()> rec = [&]() {
    auto hash_pos = make_pair(mask_covered, mask_pieces);

    if (mem.count(hash_pos)) {
      return mem[hash_pos];
    }

    if (ptr == 2 * K) {
      mem[hash_pos] = false;
      return false;
    }

    ull mask_covered_anti = ~mask_covered;

    while (mask_covered_anti > 0) {
      int b = __builtin_ctzll(mask_covered_anti);
      mask_covered_anti &= ~(1ULL << b);
      int i = b / N;
      int j = b % N;

      int p = order[ptr];

      if (mask_pieces & mask_cover[i][j][p]) {
        continue;
      }

      ull sf_covered = mask_covered;
      mask_pieces |= (1ULL << (i * N + j));
      mask_covered |= mask_cover[i][j][p];
      ++ptr;

      auto res = rec();

      --ptr;
      mask_pieces &= ~(1ULL << (i * N + j));
      mask_covered = sf_covered;

      if (!res) {
        mem[hash_pos] = true;
        return true;
      }
    }
    mem[hash_pos] = false;
    return false;
  };
  cout << (rec() ? "Alice" : "Bob") << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 112ms
memory: 17580kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

score: 0
Accepted
time: 11ms
memory: 5352kb

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 30ms
memory: 9640kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

score: 0
Accepted
time: 27ms
memory: 7864kb

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 32ms
memory: 9144kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 41ms
memory: 9840kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 70ms
memory: 14348kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

score: 0
Accepted
time: 30ms
memory: 7812kb

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

score: 0
Accepted
time: 11ms
memory: 5516kb

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

score: 0
Accepted
time: 11ms
memory: 5484kb

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

score: 0
Accepted
time: 11ms
memory: 5276kb

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

score: 0
Accepted
time: 88ms
memory: 14636kb

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 517ms
memory: 51496kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 45ms
memory: 10132kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 146ms
memory: 21420kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 104ms
memory: 17608kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 356ms
memory: 41768kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 482ms
memory: 54624kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1224ms
memory: 112448kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 205ms
memory: 27228kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed