QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546291 | #1811. How to Move the Beans | surgutti# | WA | 7ms | 32980kb | C++17 | 1.8kb | 2024-09-03 22:26:05 | 2024-09-03 22:26:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int N = 1000 + 7;
int h, w;
string s[N];
vector<int> adj[N * N];
int mat[N * N];
int vis[N * N], col = 1;
const int dx[] = {-1, 0, +1, 0};
const int dy[] = {0, -1, 0, +1};
bool dfs(int u) {
if (vis[u] == col)
return false;
vis[u] = col;
for (int v : adj[u])
if (mat[v] == -1) {
mat[v] = u;
mat[u] = v;
return true;
}
for (int v : adj[u])
if (dfs(mat[v])) {
mat[v] = u;
mat[u] = v;
return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> h >> w;
rep(i, h) cin >> s[i];
rep(i, h) rep(j, w) {
mat[i * w + j] = -1;
if (s[i][j] == '#')
continue;
rep(d, 4) {
int r = i + dx[d];
int c = (j + dy[d]) % w;
if (0 <= r && r < h && s[r][c] != '#' && (r != i || c != j)) {
adj[i * w + j].push_back(r * w + j);
}
}
}
rep(i, h) rep(j, w) if (mat[i * w + j] == -1) {
if (!dfs(i * w + j)) {
col++;
dfs(i * w + j);
}
}
int won = 0;
int lost = 0;
rep(i, h) rep(j, w) {
if (s[i][j] == 'B') {
int u = i * w + j;
if (mat[u] == -1) {
lost++;
}
else {
int v = mat[u];
mat[u] = -1;
mat[v] = -1;
vis[u] = col;
bool fail = false;
for (int x : adj[u]) {
if (dfs(x)) {
fail = true;
break;
}
}
if (!fail) {
vis[u] = ++col;
for (int x : adj[u]) {
if (dfs(x)) {
fail = true;
break;
}
}
}
if (fail)
lost++;
else
won++;
}
}
}
// cerr << "won: " << won << '\n';
// cerr << "lost: " << lost << '\n';
if (won % 2 == 0)
cout << "Bob\n";
else
cout << "Alice\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 29900kb
input:
2 3 B.# #..
output:
Alice
result:
ok "Alice"
Test #2:
score: 0
Accepted
time: 4ms
memory: 30124kb
input:
1 1 B
output:
Bob
result:
ok "Bob"
Test #3:
score: 0
Accepted
time: 3ms
memory: 31220kb
input:
1 3 B#.
output:
Alice
result:
ok "Alice"
Test #4:
score: 0
Accepted
time: 4ms
memory: 30924kb
input:
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
output:
Bob
result:
ok "Bob"
Test #5:
score: -100
Wrong Answer
time: 7ms
memory: 32980kb
input:
293 249 #B..B..BBB..B.B.B...#BBB..B#B.BBB.#B##B.BB.B.##B#B.BB..B.#B#BB.BB##B#BB#...B..BB..B.B##B.B#B.#.##..B.#..BBBB#.BB..#.BBB#B##BB....B.##B..#...B#..B.BB#B.#...B#.BB.#B#.B...BBB.B.B..B....##.B..B##.BB#B.B.BBB.B#B..#.B.B#.B##..B#.##BB.#BB#.BB.#.B..BB.BB.B BB.B.#.B#BB.B.B..B.###.B...BB.##.B...B#BB....
output:
Bob
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'