QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18149#2213. KnightGemini7X#AC ✓392ms100564kbC++141.9kb2022-01-16 15:49:132022-05-04 17:12:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 17:12:44]
  • 评测
  • 测评结果:AC
  • 用时:392ms
  • 内存:100564kb
  • [2022-01-16 15:49:13]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1000005;
template <typename T>
void read(T &x) {
	T flg = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') flg = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= flg;
}
int n, m, r, c;
int dx[4] = {1, 1, -1, -1};
int dy[4] = {1, -1, 1, -1};
char mp[1005][1005];
int sa, sb;
vector<int> vec[maxn];
bool check(int x, int y) {
	if (x < 1 || x > n || y < 1 || y > m) return false;
	if (mp[x][y] == '@') return false;
	return true;
}
bool judge(int x) {
	for (int y : vec[x]) {
		int i = (y + m - 1) / m, j = y - (i - 1) * m;
		if (mp[i][j] == '.') return true;
	}
	return false;
}
int pos[maxn], col[maxn], zz;
void dfs(int u, int cc) {
	pos[u] = zz;
	col[u] = cc;
	for (int v : vec[u]) {
		if (pos[v] == -1) dfs(v, cc ^ 1);
	}
}
int main() {
	read(n); read(m); read(r); read(c);
	for (int i = 1; i <= n; i++) {
		scanf("%s", mp[i] + 1);
		for (int j = 1; j <= m; j++) {
			if (mp[i][j] == 'A') {
				sa = (i - 1) * m + j;
			}
			if (mp[i][j] == 'B') {
				sb = (i - 1) * m + j;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mp[i][j] != '@') {
				for (int k = 0; k < 4; k++) {
					int x = i + r * dx[k], y = j + c * dy[k];
					if (check(x, y)) {
						vec[(i - 1) * m + j].pb((x - 1) * m + y);
					}
					x = i + c * dx[k], y = j + r * dy[k];
					if (check(x, y)) {
						vec[(i - 1) * m + j].pb((x - 1) * m + y);
					}
				}
			}
		}
	}
	if (!judge(sa)) {
		puts("Bob");
	} else {
		for (int i = 1; i <= n * m; i++) pos[i] = -1;
		for (int i = 1; i <= n * m; i++) {
			if (pos[i] == -1) {
				zz++;
				dfs(i, 0);
			}
		}
		if (pos[sa] != pos[sb]) puts("Alice");
		else if (col[sa] == col[sb]) puts("Alice");
		else puts("Bob");
	}
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 41ms
memory: 43556kb

Test #2:

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

Test #3:

score: 0
Accepted
time: 142ms
memory: 52916kb

Test #4:

score: 0
Accepted
time: 65ms
memory: 41128kb

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 134ms
memory: 52280kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

score: 0
Accepted
time: 108ms
memory: 52020kb

Test #29:

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

Test #30:

score: 0
Accepted
time: 21ms
memory: 35148kb

Test #31:

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

Test #32:

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

Test #33:

score: 0
Accepted
time: 111ms
memory: 48460kb

Test #34:

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

Test #35:

score: 0
Accepted
time: 87ms
memory: 45880kb

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

score: 0
Accepted
time: 28ms
memory: 36944kb

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

score: 0
Accepted
time: 128ms
memory: 47276kb

Test #49:

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

Test #50:

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

Test #51:

score: 0
Accepted
time: 233ms
memory: 67196kb

Test #52:

score: 0
Accepted
time: 252ms
memory: 66828kb

Test #53:

score: 0
Accepted
time: 61ms
memory: 40972kb

Test #54:

score: 0
Accepted
time: 365ms
memory: 85984kb

Test #55:

score: 0
Accepted
time: 169ms
memory: 52432kb

Test #56:

score: 0
Accepted
time: 351ms
memory: 83992kb

Test #57:

score: 0
Accepted
time: 141ms
memory: 52032kb

Test #58:

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

Test #59:

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

Test #60:

score: 0
Accepted
time: 372ms
memory: 87720kb

Test #61:

score: 0
Accepted
time: 141ms
memory: 50700kb

Test #62:

score: 0
Accepted
time: 101ms
memory: 45648kb

Test #63:

score: 0
Accepted
time: 264ms
memory: 68948kb

Test #64:

score: 0
Accepted
time: 64ms
memory: 40976kb

Test #65:

score: 0
Accepted
time: 322ms
memory: 79464kb

Test #66:

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

Test #67:

score: 0
Accepted
time: 200ms
memory: 56600kb

Test #68:

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

Test #69:

score: 0
Accepted
time: 329ms
memory: 91308kb

Test #70:

score: 0
Accepted
time: 112ms
memory: 47164kb

Test #71:

score: 0
Accepted
time: 105ms
memory: 48716kb

Test #72:

score: 0
Accepted
time: 35ms
memory: 39596kb

Test #73:

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

Test #74:

score: 0
Accepted
time: 347ms
memory: 84160kb

Test #75:

score: 0
Accepted
time: 175ms
memory: 54792kb

Test #76:

score: 0
Accepted
time: 177ms
memory: 56948kb

Test #77:

score: 0
Accepted
time: 286ms
memory: 74336kb

Test #78:

score: 0
Accepted
time: 53ms
memory: 39620kb

Test #79:

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

Test #80:

score: 0
Accepted
time: 194ms
memory: 57344kb

Test #81:

score: 0
Accepted
time: 156ms
memory: 55256kb

Test #82:

score: 0
Accepted
time: 152ms
memory: 52472kb

Test #83:

score: 0
Accepted
time: 78ms
memory: 43900kb

Test #84:

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

Test #85:

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

Test #86:

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

Test #87:

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

Test #88:

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

Test #89:

score: 0
Accepted
time: 319ms
memory: 83416kb

Test #90:

score: 0
Accepted
time: 144ms
memory: 52768kb

Test #91:

score: 0
Accepted
time: 39ms
memory: 39748kb

Test #92:

score: 0
Accepted
time: 321ms
memory: 77092kb

Test #93:

score: 0
Accepted
time: 42ms
memory: 35364kb

Test #94:

score: 0
Accepted
time: 311ms
memory: 78108kb

Test #95:

score: 0
Accepted
time: 232ms
memory: 73924kb

Test #96:

score: 0
Accepted
time: 176ms
memory: 56360kb

Test #97:

score: 0
Accepted
time: 262ms
memory: 82768kb

Test #98:

score: 0
Accepted
time: 283ms
memory: 68684kb

Test #99:

score: 0
Accepted
time: 241ms
memory: 66776kb

Test #100:

score: 0
Accepted
time: 287ms
memory: 68468kb

Test #101:

score: 0
Accepted
time: 348ms
memory: 80112kb

Test #102:

score: 0
Accepted
time: 255ms
memory: 77288kb

Test #103:

score: 0
Accepted
time: 326ms
memory: 79584kb

Test #104:

score: 0
Accepted
time: 99ms
memory: 45940kb

Test #105:

score: 0
Accepted
time: 233ms
memory: 63972kb

Test #106:

score: 0
Accepted
time: 131ms
memory: 55076kb

Test #107:

score: 0
Accepted
time: 299ms
memory: 75808kb

Test #108:

score: 0
Accepted
time: 361ms
memory: 86060kb

Test #109:

score: 0
Accepted
time: 216ms
memory: 60936kb

Test #110:

score: 0
Accepted
time: 375ms
memory: 77688kb

Test #111:

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

Test #112:

score: 0
Accepted
time: 321ms
memory: 73520kb

Test #113:

score: 0
Accepted
time: 28ms
memory: 32936kb

Test #114:

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

Test #115:

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

Test #116:

score: 0
Accepted
time: 271ms
memory: 73344kb

Test #117:

score: 0
Accepted
time: 374ms
memory: 81268kb

Test #118:

score: 0
Accepted
time: 31ms
memory: 37976kb

Test #119:

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

Test #120:

score: 0
Accepted
time: 238ms
memory: 68580kb

Test #121:

score: 0
Accepted
time: 49ms
memory: 41864kb

Test #122:

score: 0
Accepted
time: 72ms
memory: 49240kb

Test #123:

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

Test #124:

score: 0
Accepted
time: 72ms
memory: 43264kb

Test #125:

score: 0
Accepted
time: 166ms
memory: 51212kb

Test #126:

score: 0
Accepted
time: 46ms
memory: 39924kb

Test #127:

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

Test #128:

score: 0
Accepted
time: 136ms
memory: 60472kb

Test #129:

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

Test #130:

score: 0
Accepted
time: 241ms
memory: 63480kb

Test #131:

score: 0
Accepted
time: 49ms
memory: 39640kb

Test #132:

score: 0
Accepted
time: 225ms
memory: 61308kb

Test #133:

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

Test #134:

score: 0
Accepted
time: 114ms
memory: 48864kb

Test #135:

score: 0
Accepted
time: 337ms
memory: 87080kb

Test #136:

score: 0
Accepted
time: 31ms
memory: 31256kb

Test #137:

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

Test #138:

score: 0
Accepted
time: 360ms
memory: 90056kb

Test #139:

score: 0
Accepted
time: 42ms
memory: 39028kb

Test #140:

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

Test #141:

score: 0
Accepted
time: 324ms
memory: 72348kb

Test #142:

score: 0
Accepted
time: 39ms
memory: 37504kb

Test #143:

score: 0
Accepted
time: 392ms
memory: 91876kb

Test #144:

score: 0
Accepted
time: 188ms
memory: 54680kb

Test #145:

score: 0
Accepted
time: 254ms
memory: 68160kb

Test #146:

score: 0
Accepted
time: 107ms
memory: 46296kb

Test #147:

score: 0
Accepted
time: 361ms
memory: 83960kb

Test #148:

score: 0
Accepted
time: 307ms
memory: 77068kb

Test #149:

score: 0
Accepted
time: 217ms
memory: 62916kb

Test #150:

score: 0
Accepted
time: 310ms
memory: 76876kb

Test #151:

score: 0
Accepted
time: 379ms
memory: 100564kb

Test #152:

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

Test #153:

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

Test #154:

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

Test #155:

score: 0
Accepted
time: 303ms
memory: 74064kb

Test #156:

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

Test #157:

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

Test #158:

score: 0
Accepted
time: 139ms
memory: 52696kb

Test #159:

score: 0
Accepted
time: 19ms
memory: 32652kb

Test #160:

score: 0
Accepted
time: 62ms
memory: 40652kb

Test #161:

score: 0
Accepted
time: 132ms
memory: 49060kb

Test #162:

score: 0
Accepted
time: 61ms
memory: 42464kb

Test #163:

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

Test #164:

score: 0
Accepted
time: 217ms
memory: 59280kb

Test #165:

score: 0
Accepted
time: 382ms
memory: 80876kb

Test #166:

score: 0
Accepted
time: 283ms
memory: 72556kb