QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230571#7635. Fairy Chessucup-team2303#AC ✓1012ms65632kbC++173.3kb2023-10-28 19:36:042023-10-28 19:36:05

Judging History

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

  • [2023-10-28 19:36:05]
  • 评测
  • 测评结果:AC
  • 用时:1012ms
  • 内存:65632kb
  • [2023-10-28 19:36:04]
  • 提交

answer

// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define PB emplace_back
// #define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) {rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1];}

char s[15];
int p[9][9], dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, t[9][9];
#define ull unsigned long long
#define MP make_pair
map<pair<ull, ull>, bool> mp[13];

bool R(int n, int m, int k) {
	bool o = 1;
	for(int x = n - 1, y = m - 1; x && y; --x, --y) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	for(int x = n + 1, y = m - 1; x <= 8 && y; ++x, --y) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	for(int x = n - 1, y = m + 1; x && y <= 8; --x, ++y) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	for(int x = n + 1, y = m + 1; x <= 8 && y <= 8; ++x, ++y) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	return o;
}
bool G(int n, int m, int k) {
	bool o = 1;
	for(int x = n - 1, y = m; x; --x) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	for(int x = n + 1, y = m; x <= 8; ++x) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	for(int x = n, y = m - 1; y; --y) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	for(int x = n, y = m + 1; y <= 8; ++y) {
		p[x][y] += k;
		o &= !t[x][y];
	}
	return o;
}
bool B(int n, int m, int k) {
	bool o = 1;
	rep(i, 0, 7) {
		int x = n + dx[i], y = m + dy[i];
		if(x >= 1 && x <= 8 && y >= 1 && y <= 8) {
			p[x][y] += k;
			o &= !t[x][y];
		}
	}
	return o;
}
bool ins(int n, int m, char o, int k) {
	p[n][m] += k;
	t[n][m] += k;
	bool q = 1;
	if(o == 'B') q = R(n, m, k);
	else if(o == 'R') q = G(n, m, k);
	else if(o == 'Q') q = R(n, m, k) & G(n, m, k);
	else if(o == 'A') q = R(n, m, k) & B(n, m, k);
	else if(o == 'C') q = G(n, m, k) & B(n, m, k);
	else if(o == 'M') q = R(n, m, k) & G(n, m, k) & B(n, m, k);
	if(!q) {
		// cout << p[n][m] << ' ' << ' ' << t[n][m] << ' ' << k << endl;
		p[n][m] -= k, t[n][m] -= k;
		if(o == 'B') R(n, m, -k);
		else if(o == 'R') G(n, m, -k);
		else if(o == 'Q') R(n, m, -k), G(n, m, -k);
		else if(o == 'A') R(n, m, -k), B(n, m, -k);
		else if(o == 'C') G(n, m, -k), B(n, m, -k);
		else if(o == 'M') R(n, m, -k), G(n, m, -k), B(n, m, -k);
	}
	return q;
}
bool dfs(int n) {
	if(n > 12) return 0;
	ull sp = 0;
	rep(i, 1, 8) rep(j, 1, 8) sp |= ((ull) (!p[i][j])) << ((i - 1) * 8 + j - 1);
	ull sq = 0;
	rep(i, 1, 8) rep(j, 1, 8) sq |= ((ull) (t[i][j])) << ((i - 1) * 8 + j - 1);
	if(!sp) return 0;
	if(mp[n].count(MP(sp, sq))) return mp[n][MP(sp, sq)];
	rep(i, 1, 8) rep(j, 1, 8) if(!p[i][j]) {
		if(n == 1 && i > j) continue;
		if(ins(i, j, s[n], 1)) {
			if(!dfs(n + 1)) {
				ins(i, j, s[n], -1);
				return mp[n][MP(sp, sq)] = 1;
			}
			ins(i, j, s[n], -1);
		}
	}
	return mp[n][MP(sp, sq)] = 0;
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s + 1;
	dfs(1) ? cout << "Alice" : cout << "Bob";
	return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 107ms
memory: 11828kb

input:

BBAARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

input:

BAMBAMQQRCCR

output:

Alice

result:

ok single line: 'Alice'

Test #3:

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

input:

QQRAACMRMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #4:

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

input:

MBBARQRMACQC

output:

Alice

result:

ok single line: 'Alice'

Test #5:

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

input:

ACQCMQRBBRMA

output:

Alice

result:

ok single line: 'Alice'

Test #6:

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

input:

MRCMABRQCQAB

output:

Alice

result:

ok single line: 'Alice'

Test #7:

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

input:

BBRCMMQAAQRC

output:

Alice

result:

ok single line: 'Alice'

Test #8:

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

input:

RRMCQMACABQB

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

input:

QMQBMRBACACR

output:

Alice

result:

ok single line: 'Alice'

Test #10:

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

input:

CMRQAQCBBRAM

output:

Alice

result:

ok single line: 'Alice'

Test #11:

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

input:

CABCRQMMRQAB

output:

Alice

result:

ok single line: 'Alice'

Test #12:

score: 0
Accepted
time: 68ms
memory: 8756kb

input:

ARCBBCMQRAQM

output:

Alice

result:

ok single line: 'Alice'

Test #13:

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

input:

ARCMCARMQBBQ

output:

Alice

result:

ok single line: 'Alice'

Test #14:

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

input:

AQABMCQCMRRB

output:

Bob

result:

ok single line: 'Bob'

Test #15:

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

input:

ACMRABRQMCBQ

output:

Alice

result:

ok single line: 'Alice'

Test #16:

score: 0
Accepted
time: 37ms
memory: 7192kb

input:

CBARMBCQMQAR

output:

Bob

result:

ok single line: 'Bob'

Test #17:

score: 0
Accepted
time: 58ms
memory: 7996kb

input:

RBABRQMCAMQC

output:

Bob

result:

ok single line: 'Bob'

Test #18:

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

input:

MBCQBQARRMCA

output:

Alice

result:

ok single line: 'Alice'

Test #19:

score: 0
Accepted
time: 25ms
memory: 6164kb

input:

AMBQRBCQACMR

output:

Bob

result:

ok single line: 'Bob'

Test #20:

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

input:

QRAMQMBBCRAC

output:

Alice

result:

ok single line: 'Alice'

Test #21:

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

input:

ARBCQMMBARQC

output:

Alice

result:

ok single line: 'Alice'

Test #22:

score: 0
Accepted
time: 79ms
memory: 11000kb

input:

CACAMBRQQRBM

output:

Bob

result:

ok single line: 'Bob'

Test #23:

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

input:

CQRRMMBQABCA

output:

Bob

result:

ok single line: 'Bob'

Test #24:

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

input:

ABABCQRMMCRQ

output:

Alice

result:

ok single line: 'Alice'

Test #25:

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

input:

CMBRAAQRQMBC

output:

Bob

result:

ok single line: 'Bob'

Test #26:

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

input:

AQBMRMQRBACC

output:

Alice

result:

ok single line: 'Alice'

Test #27:

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

input:

BRACQQMCAMBR

output:

Bob

result:

ok single line: 'Bob'

Test #28:

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

input:

MCCAQBMQRABR

output:

Bob

result:

ok single line: 'Bob'

Test #29:

score: 0
Accepted
time: 40ms
memory: 7440kb

input:

RBQBCRAACMQM

output:

Bob

result:

ok single line: 'Bob'

Test #30:

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

input:

ACRQARMBBQMC

output:

Bob

result:

ok single line: 'Bob'

Test #31:

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

input:

MRCQBCBQRMAA

output:

Alice

result:

ok single line: 'Alice'

Test #32:

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

input:

ACRQQCMMBBAR

output:

Bob

result:

ok single line: 'Bob'

Test #33:

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

input:

MMACQBRQABRC

output:

Bob

result:

ok single line: 'Bob'

Test #34:

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

input:

QACMQABRMCBR

output:

Alice

result:

ok single line: 'Alice'

Test #35:

score: 0
Accepted
time: 24ms
memory: 5768kb

input:

ACAQRCMRMBQB

output:

Alice

result:

ok single line: 'Alice'

Test #36:

score: 0
Accepted
time: 25ms
memory: 5808kb

input:

RABQCQMCABMR

output:

Bob

result:

ok single line: 'Bob'

Test #37:

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

input:

QQBARCRBMMAC

output:

Alice

result:

ok single line: 'Alice'

Test #38:

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

input:

RQMRQABCABCM

output:

Alice

result:

ok single line: 'Alice'

Test #39:

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

input:

RQAMBRQCCBMA

output:

Alice

result:

ok single line: 'Alice'

Test #40:

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

input:

QQBACMARMRBC

output:

Alice

result:

ok single line: 'Alice'

Test #41:

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

input:

QAQCRRAMMCBB

output:

Alice

result:

ok single line: 'Alice'

Test #42:

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

input:

QQBMCBRARMAC

output:

Bob

result:

ok single line: 'Bob'

Test #43:

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

input:

BABARRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #44:

score: 0
Accepted
time: 753ms
memory: 47828kb

input:

BBARARCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #45:

score: 0
Accepted
time: 90ms
memory: 10632kb

input:

BBAARCRCQQMM

output:

Alice

result:

ok single line: 'Alice'

Test #46:

score: 0
Accepted
time: 159ms
memory: 14148kb

input:

BBAARRCQCQMM

output:

Bob

result:

ok single line: 'Bob'

Test #47:

score: 0
Accepted
time: 118ms
memory: 12016kb

input:

BBAARRCCQMQM

output:

Bob

result:

ok single line: 'Bob'

Test #48:

score: 0
Accepted
time: 350ms
memory: 26532kb

input:

BBAACCRQMQRM

output:

Bob

result:

ok single line: 'Bob'

Test #49:

score: 0
Accepted
time: 346ms
memory: 27308kb

input:

BACBACQRRQMM

output:

Bob

result:

ok single line: 'Bob'

Test #50:

score: 0
Accepted
time: 1012ms
memory: 65632kb

input:

RAABBRCCQQMM

output:

Bob

result:

ok single line: 'Bob'

Test #51:

score: 0
Accepted
time: 77ms
memory: 9000kb

input:

RABRBQMCACQM

output:

Bob

result:

ok single line: 'Bob'

Test #52:

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

input:

CMMQQABCRABR

output:

Alice

result:

ok single line: 'Alice'

Test #53:

score: 0
Accepted
time: 338ms
memory: 26204kb

input:

RBAABRCCQQMM

output:

Alice

result:

ok single line: 'Alice'

Extra Test:

score: 0
Extra Test Passed