QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418890#7635. Fairy Chess1e11#AC ✓245ms26660kbC++203.2kb2024-05-23 16:19:522024-05-23 16:19:53

Judging History

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

  • [2024-05-23 16:19:53]
  • 评测
  • 测评结果:AC
  • 用时:245ms
  • 内存:26660kb
  • [2024-05-23 16:19:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ll = long long;
#define SZ(v) (ll)((v).size())
#define pb emplace_back
#define AI(i) begin(i), end(i)
#define X first
#define Y second
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

using u64 = unsigned long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  string s;
  cin >> s;

  vector maskBishop(8, vector<u64>(8));
  vector maskRook(8, vector<u64>(8));
  vector maskKnight(8, vector<u64>(8));

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

  for (int i = 0; i < 8; i++) {
	  for (int j = 0; j < 8; j++) {
		  int x = i, y = j;
		  for (auto [dx, dy] : {pair(1, 1), {1, -1}, {-1, -1}, {-1, 1}}) {
			  int nx = x + dx, ny = y + dy;
			  while (in(nx, ny)) {
				  maskBishop[i][j] |= 1ull << nx * 8 + ny;
				  nx += dx, ny += dy;
			  }
		  }
	  }
  }

  for (int i = 0; i < 8; i++) {
	  for (int j = 0; j < 8; j++) {
		  int x = i, y = j;
		  for (auto [dx, dy] : {pair(1, 0), {0, 1}, {-1, 0}, {0, -1}}) {
			  int nx = x + dx, ny = y + dy;
			  while (in(nx, ny)) {
				  maskRook[i][j] |= 1ull << nx * 8 + ny;
				  nx += dx, ny += dy;
			  }
		  }
	  }
  }

  for (int i = 0; i < 8; i++) {
	  for (int j = 0; j < 8; j++) {
		  int x = i, y = j;
		  for (auto [dx, dy] : {pair(2, 1), {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}) {
			  int nx = x + dx, ny = y + dy;
			  if (in(nx, ny)) {
				  maskKnight[i][j] |= 1ull << nx * 8 + ny;
			  }
		  }
	  }
  }

  vector mp(12, map<pair<u64, u64>, bool>());

  vector<vector<int>> cands(2);
  for (int i = 0; i < 4; i++) {
	  for (int j = 0; j <= i; j++) {
		  cands[0].emplace_back(8 * i + j);
	  }
  }
  cands[1].resize(64);
  iota(cands[1].begin(), cands[1].end(), 0);

  auto dfs = [&](auto dfs, int t, u64 atk, u64 occ) -> bool {
	  if (t == 12) {
		  return false;
	  }
	  if (mp[t].count({atk, occ})) {
		  return mp[t][{atk, occ}];
	  }
	  for (auto id : cands[t != 0]) {
		  int i = id / 8, j = id % 8;
		  if (atk >> id & 1 | occ >> id & 1) {
			  continue;
		  }
		  u64 natk = 0;
		  if (s[t] == 'B') {
			  natk |= maskBishop[i][j];
		  } else if (s[t] == 'R') {
			  natk |= maskRook[i][j];
		  } else if (s[t] == 'Q') {
			  natk |= maskBishop[i][j] | maskRook[i][j];
		  } else if (s[t] == 'A') {
			  natk |= maskBishop[i][j] | maskKnight[i][j];
		  } else if (s[t] == 'C') {
			  natk |= maskRook[i][j] | maskKnight[i][j];
		  } else if (s[t] == 'M') {
			  natk |= maskBishop[i][j] | maskRook[i][j] | maskKnight[i][j];
		  }
		  if (natk & occ) {
			  continue;
		  }
		  if (!dfs(dfs, t + 1, atk | natk, occ | 1ull << id)) {
			  return mp[t][{atk, occ}] = true;
		  }

	  }
	  return mp[t][{atk, occ}] = false;
  };

  cout << (dfs(dfs, 0, 0ull, 0ull) ? "Alice" : "Bob") << '\n';

  return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 6856kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

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

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

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

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

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

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

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

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

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

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

score: 0
Accepted
time: 55ms
memory: 10376kb

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

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

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

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

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

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

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 245ms
memory: 26660kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 44ms
memory: 9200kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

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

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

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

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 66ms
memory: 11628kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 29ms
memory: 7620kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 148ms
memory: 19764kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

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

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 155ms
memory: 21316kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed