QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104709 | #6314. 过河卒 | abcdefg | 100 ✓ | 679ms | 54296kb | C++17 | 7.4kb | 2023-05-11 19:09:44 | 2023-05-11 19:09:47 |
Judging History
answer
#include <bits/stdc++.h>
#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#else
#define dbg(x...) (0)
#endif
using namespace std;
using ll = long long;
// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))
template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
if (y < x) x = y;
}
namespace qingwa {
const int N = 12;
const int M = N * N * N * N * N * N + 9;
const int dx[] = {1, 0, 0, -1};
const int dy[] = {0, -1, 1, 0};
int n, m, a[M], du[M], du_[M], mn[M], mx[M], x0, y0, x1, y1, x2, y2;
bool ban[N][N];
inline int Id(int x0, int y0, int x1, int y1, int x2, int y2) {
return (x0 - 1) * m * n * m * n * m + (y0 - 1) * n * m * n * m + (x1 - 1) * m * n * m +
(y1 - 1) * n * m + (x2 - 1) * m + y2;
}
inline void De(int t, int &x0, int &y0, int &x1, int &y1, int &x2, int &y2) {
--t;
x0 = t / (m * n * m * n * m) + 1, t %= (m * n * m * n * m);
y0 = t / (n * m * n * m) + 1, t %= (n * m * n * m);
x1 = t / (m * n * m) + 1, t %= (m * n * m);
y1 = t / (n * m) + 1, t %= (n * m);
x2 = t / (m) + 1, t %= (m);
y2 = t + 1;
}
// 合法
inline bool Can(int x0, int y0, int x1, int y1, int x2, int y2) {
if (min({x0, y0, x1, y1, x2, y2}) <= 0 || max({x0, x1, x2}) > n || max({y0, y1, y2}) > m)
return 0;
if (ban[x0][y0] || ban[x1][y1] || ban[x2][y2]) return 0;
if (x1 == x2 && y1 == y2) return 0;
return 1;
}
// 1: zu, 2 last
inline int End(int x0, int y0, int x1, int y1, int x2, int y2) {
if (x0 == 1) return 1;
if (x0 == x1 && y0 == y1) return 2;
if (x0 == x2 && y0 == y2) return 2;
// if (!du[Id(x0, y0, x1, y1, x2, y2)]) return 2;
return 0;
}
inline void Nor(int &x1, int &y1, int &x2, int &y2) {
if (make_pair(x1, y1) > make_pair(x2, y2)) swap(x1, x2), swap(y1, y2);
}
inline void CalcDeg() {
memset(du_, 0, sizeof du_);
re (i0, n)
re (j0, m)
re (i1, n)
re (j1, m)
re (i2, n)
re (j2, m) {
if (make_pair(i1, j1) > make_pair(i2, j2) || !Can(i0, j0, i1, j1, i2, j2) ||
End(i0, j0, i1, j1, i2, j2))
continue;
int id = Id(i0, j0, i1, j1, i2, j2);
// zu go
if ((i0 ^ j0 ^ i1 ^ j1 ^ i2 ^ j2 ^ x0 ^ y0 ^ x1 ^ y1 ^ x2 ^ y2) & 1)
rep (d, 1, 3) {
int n0 = i0 + dx[d], m0 = j0 + dy[d];
if (Can(n0, m0, i1, j1, i2, j2)) ++du_[id];
}
// shuai go
else
rep (d, 0, 3) {
int n1 = i1 + dx[d], m1 = j1 + dy[d], n2 = i2, m2 = j2;
Nor(n1, m1, n2, m2);
if (Can(i0, j0, n1, m1, n2, m2)) ++du_[id];
n1 = i1, m1 = j1, n2 = i2 + dx[d], m2 = j2 + dy[d];
Nor(n1, m1, n2, m2);
if (Can(i0, j0, n1, m1, n2, m2)) ++du_[id];
}
}
}
inline void Topo() {
memset(a, 0, sizeof a);
memset(mn, 0x3f, sizeof mn);
memset(mx, ~0x3f, sizeof mx);
queue<int> q;
re (i, Id(n, m, n, m, n, m)) du[i] = du_[i];
re (i0, n)
re (j0, m)
re (i1, n)
re (j1, m)
re (i2, n)
re (j2, m) {
if (make_pair(i1, j1) > make_pair(i2, j2) || !Can(i0, j0, i1, j1, i2, j2)) continue;
int id = Id(i0, j0, i1, j1, i2, j2);
if (auto ed = End(i0, j0, i1, j1, i2, j2); ed) {
q.push(id);
du[id] = 0;
if (ed == 1) {
a[id] = 1;
if ((i0 ^ j0 ^ i1 ^ j1 ^ i2 ^ j2 ^ x0 ^ y0 ^ x1 ^ y1 ^ x2 ^ y2) & 1)
mn[id] = 0;
else
mx[id] = 0;
} else
mx[id] = 0,
a[id] = 2 - !((i0 ^ j0 ^ i1 ^ j1 ^ i2 ^ j2 ^ x0 ^ y0 ^ x1 ^ y1 ^ x2 ^ y2) & 1);
} else if (!du[id])
q.push(id),
mx[id] = 0,
a[id] = 2 - !((i0 ^ j0 ^ i1 ^ j1 ^ i2 ^ j2 ^ x0 ^ y0 ^ x1 ^ y1 ^ x2 ^ y2) & 1);
}
while (q.size()) {
int f = q.front();
q.pop();
int i0, j0, i1, j1, i2, j2;
De(f, i0, j0, i1, j1, i2, j2);
// shuai go
if ((i0 ^ j0 ^ i1 ^ j1 ^ i2 ^ j2 ^ x0 ^ y0 ^ x1 ^ y1 ^ x2 ^ y2) & 1)
rep (d, 0, 3) {
auto Fun = [&](int n1, int m1, int n2, int m2) {
if (!Can(i0, j0, n1, m1, n2, m2) || End(i0, j0, n1, m1, n2, m2)) return;
int t = Id(i0, j0, n1, m1, n2, m2);
if (a[f] == 2) {
if (mn[t] >= 1e9) a[t] = 2, mn[t] = mx[f] + 1, q.push(t);
} else
up(mx[t], mn[f] + 1);
if (!--du[t])
if (mn[t] >= 1e9) a[t] = 1, q.push(t);
};
int n1 = i1 + dx[d], m1 = j1 + dy[d], n2 = i2, m2 = j2;
Nor(n1, m1, n2, m2);
Fun(n1, m1, n2, m2);
n1 = i1, m1 = j1, n2 = i2 + dx[d], m2 = j2 + dy[d];
Nor(n1, m1, n2, m2);
// if (i0 == 3 && j0 == 1 && i1 == 1 && j1 == 1 && i2 == 4 && j2 == 1) {
// cerr << "YES " << n1 << ' ' << m1 << ' ' << n2 << ' ' << m2 << '\n';
// }
Fun(n1, m1, n2, m2);
}
// zu go
else
rep (d, 0, 2) {
int n0 = i0 + dx[d], m0 = j0 + dy[d];
if (!Can(n0, m0, i1, j1, i2, j2) || End(n0, m0, i1, j1, i2, j2)) continue;
int t = Id(n0, m0, i1, j1, i2, j2);
if (a[f] == 1) {
if (mn[t] >= 1e9) a[t] = 1, mn[t] = mx[f] + 1, q.push(t);
} else
up(mx[t], mn[f] + 1);
if (!--du[t])
if (mn[t] >= 1e9) a[t] = 2, q.push(t);
}
}
// re (i0, n)
// re (j0, m)
// re (i1, n)
// re (j1, m)
// re (i2, n)
// re (j2, m) {
// if (make_pair(i1, j1) > make_pair(i2, j2) || !Can(i0, j0, i1, j1, i2, j2))
// continue; int id = Id(i0, j0, i1, j1, i2, j2); cerr << i0 << ' ' << j0 << ' ' << i1
// << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n'; dbg(id, a[id], mn[id], mx[id]);
// }
}
inline void Work() {
cin >> n >> m;
memset(ban, 0, sizeof ban);
x1 = 0;
re (i, n)
re (j, m) {
char c;
cin >> c;
if (c == '#')
ban[i][j] = 1;
else if (c == 'X')
x0 = i, y0 = j;
else if (c == 'O') {
if (x1)
x2 = i, y2 = j;
else
x1 = i, y1 = j;
}
}
Nor(x1, y1, x2, y2);
CalcDeg();
Topo();
int S = Id(x0, y0, x1, y1, x2, y2);
// dbg(S);
if (a[S] == 1)
cout << "Black " << mx[S] << '\n';
else if (a[S] == 2)
cout << "Red " << mn[S] << '\n';
else
cout << "Tie\n";
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T >> T;
while (T--) Work();
return 0;
}
} // namespace qingwa
signed main() { return qingwa::main(); }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 433ms
memory: 54276kb
input:
1 10 10 10 .#......#. ..#....#.. #..#..#..# ..#.O..#.. .#......#. ...####... ##..X...## .......... .##.O####. .......... 10 10 .##..##... .....##... ..X#.#.... #........# ..#.#.#... .#...#.#.. #..#.#.#.. ..#..#.#.# ...##O#... ..##O#.#.. 4 1 O O # X 10 10 .##.....## ...#....## .#.#...#.. .O###..... #...
output:
Tie Black 0 Black 0 Tie Black 0 Tie Black 0 Black 0 Tie Tie
result:
ok 10 lines
Test #2:
score: 5
Accepted
time: 374ms
memory: 54152kb
input:
2 10 10 10 .#.####..# .##..##### ##.###X### #....####. .#.####### #.#O###.## ..##.####. ..######## ########## ##O#.#.### 10 10 ..#.###.## ......#..# ....#O.... #..#.....# ...#.##### .....#..#. ..#.....#O X#....###. #.....##.. .#..##.... 10 10 .......##. .O##...##. ..#....... ####..O... ....#...## .....
output:
Black 0 Tie Tie Black 0 Black 0 Tie Black 0 Tie Tie Black 0
result:
ok 10 lines
Test #3:
score: 5
Accepted
time: 396ms
memory: 54168kb
input:
3 10 10 10 ##.####### ###..###OO ##X####.## ...####### #..###...# ##...##### ##..#.#### ..##..##.# ###..#.#.# #.###..##. 10 10 .##..##... .....##... ..X#.#.... #........# ..#.#.#... .#...#.#.. #..#.#.#.. ..#..#.#.# ...##O#... ..##O#.#.. 10 10 .......... .X........ .......... .......... ..#....... .....
output:
Black 0 Black 0 Black 0 Black 0 Black 0 Tie Tie Tie Tie Tie
result:
ok 10 lines
Test #4:
score: 5
Accepted
time: 307ms
memory: 54168kb
input:
4 10 10 10 .#......#. ..#....#.. #..#..#..# ..#.O..#.. .#......#. ...####... ##..X...## .......... .##.O####. .......... 10 10 ...#.##... ..####.##. ###.###### .####O#.X# ...####..# .##O#..#.# ##.#..###. #.#.#....# .#.#####.# .##.#.#.## 3 2 OO ## #X 10 10 .##.##...# ..##..#.#O .#O#.#...# #.#.#..##. ...
output:
Tie Black 0 Black 0 Black 0 Black 0 Black 0 Tie Tie Tie Tie
result:
ok 10 lines
Test #5:
score: 5
Accepted
time: 527ms
memory: 54156kb
input:
5 10 10 10 .......... ....O..... .......... ...X...... .......... .......... .......... .......... ########## .......O.. 10 10 .......... ..O....... .......... .......... .......... X......... .......... .......... ########## .......O.. 10 1 . . . O . . . X # O 10 1 O . . . . . . X # O 10 10 ..........
output:
Red 9 Red 21 Black 12 Red 7 Black 8 Red 23 Black 14 Red 25 Red 23 Red 1
result:
ok 10 lines
Test #6:
score: 5
Accepted
time: 465ms
memory: 54260kb
input:
6 10 10 10 .....O.... .......... .......... .......... .......... .X........ .......... .......... ########## ...O...... 10 1 O . . . . . . X # O 10 10 .......... ..O....... .......... .......... .......... X......... .......... .......... ########## .......O.. 10 10 .......... .....O.... .............
output:
Red 17 Red 7 Red 21 Red 17 Black 2 Black 12 Black 6 Red 25 Red 23 Black 10
result:
ok 10 lines
Test #7:
score: 5
Accepted
time: 59ms
memory: 50092kb
input:
7 10 10 1 . O # . . X . # . O 10 1 O . . . . . . X . O 10 1 . . # O O # # . . X 5 1 O O . X . 10 1 O # . . . . . X . O 9 1 O # O . . . . . X 10 1 . . . . X O . # . O 10 1 O O . # . . . . . X 10 1 . . . . . . X . O O 10 1 O . . . # X # O . .
output:
Red 5 Red 7 Black 0 Black 2 Red 11 Black 10 Red 1 Red 11 Black 12 Red 1
result:
ok 10 lines
Test #8:
score: 5
Accepted
time: 65ms
memory: 50076kb
input:
8 10 10 1 . . # . X # . O # O 10 1 . O O . X . . . . . 10 1 O O . . . . . . . X 5 1 . # O X O 10 1 O # . . . . X . . O 9 1 O # O . . . . X . 10 1 # . . . X O . # . O 10 1 O O # # . . . . . X 10 1 # . . . . . X . O O 10 1 . # O . # O . X # .
output:
Red 3 Red 3 Red 9 Red 1 Red 9 Red 5 Red 1 Black 0 Red 11 Red 3
result:
ok 10 lines
Test #9:
score: 5
Accepted
time: 69ms
memory: 50152kb
input:
9 10 10 1 # O # . . X . # . O 10 1 O . . . X . . . . O 10 1 . . # O O . # . . X 5 1 O O . X . 10 1 O # . # . . . X . O 9 1 O . # O . . . X . 10 1 . . . . X O . . . O 10 1 O O . # # . . . . X 10 1 . . . . X . # . O O 10 1 . # O # O . . X # .
output:
Red 5 Red 5 Red 5 Black 2 Red 7 Red 5 Red 1 Red 9 Black 8 Red 3
result:
ok 10 lines
Test #10:
score: 5
Accepted
time: 452ms
memory: 54212kb
input:
10 10 10 10 .###..###. .....O...# .##.#..... ..##.##.X# ##......#. #...#..... ....##...# ..#..O##.# #..#.##... .....##.#. 10 10 #...##..#. #......##. ..##....#. #.#.##..#O .O...#.##. .....##.X. .###...... ....#.#.#. .......##. ###...##.# 10 10 #.#....... ..##..##.. ..##.#X..O ....#..... #..#....#. #...
output:
Red 7 Red 5 Red 3 Black 2 Red 9 Tie Tie Red 9 Red 9 Red 7
result:
ok 10 lines
Test #11:
score: 5
Accepted
time: 518ms
memory: 54232kb
input:
11 10 10 10 ...#.....# ..#....... ##.##.###. ##...#.##X .....#...# ...#.#.O.# ..#...#... .....#.... ......#..# #...#...O# 10 10 ..###O#O#. .#.###.##. ##..#..#.. ....#X.... ........## ........## #...##.... ...#..###. ........#. ..#...#.#. 10 10 ######...# O.X.O####. #.#.#.#... #.......#. ...##...#. ....
output:
Black 8 Black 0 Black 2 Tie Tie Red 9 Tie Red 9 Red 9 Red 1
result:
ok 10 lines
Test #12:
score: 5
Accepted
time: 479ms
memory: 54248kb
input:
12 10 10 10 ##..##..O. .#........ .#.......# .......... #......... .XO##..... #......... .......... .......... .......... 5 6 #.#### #.#### #.OO## #X#### ###### 10 10 ....###### .######### O...##.### .######### ....###### ####....#. ####.####. ####.O..#. #######.#. ####....#X 10 10 .......... .........
output:
Red 1 Black 2 Red 9 Tie Red 9 Black 6 Tie Tie Red 3 Tie
result:
ok 10 lines
Test #13:
score: 5
Accepted
time: 511ms
memory: 54296kb
input:
13 10 10 10 .##...#... .#####..## #..#..#..# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 10 .##......# ..#..##..O ...#.##... ##..#O..## ..#...#... ###.....#X ..#....... .##.#.#... .#.#.#..#. #......#.# 10 10 .........# .......... O......... .......... ....O..... ....
output:
Black 6 Red 9 Red 9 Red 9 Black 8 Tie Red 7 Red 7 Tie Tie
result:
ok 10 lines
Test #14:
score: 5
Accepted
time: 679ms
memory: 54220kb
input:
14 10 10 10 .......O.. .......... .......... O......... .......... .......... .......... .......... .......X.. .......... 10 10 .##...#... .#####..## ...#..##.# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 10 .#..O...#. ...####... ##.X....## .......... .#.O..#... ....
output:
Red 27 Black 6 Tie Black 8 Red 17 Red 63 Black 12 Red 17 Black 16 Red 5
result:
ok 10 lines
Test #15:
score: 5
Accepted
time: 388ms
memory: 54124kb
input:
15 10 10 10 .########O .........# ########.# .........# .######### .......... #########. .......... .######### .......O.X 10 10 .##...#... .#####..## ...#..##.# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 8 ####.... ...#..#. .###..#. ...#.O#. ##.#..#. ...####. .##...
output:
Black 102 Black 6 Red 13 Red 9 Tie Red 63 Red 93 Red 139 Red 45 Black 44
result:
ok 10 lines
Test #16:
score: 5
Accepted
time: 408ms
memory: 54140kb
input:
16 10 10 10 ....###### .######### O...##.### .######### ....###### ####....#. ####.####. ####.O..#. #######.#. ####....#X 10 10 .#..O...#. ...####... ##.X....## .......... .#.O..#... .#....#... .#....#... ..####.... .......... .......... 10 10 O######### #..#..#... ..#..#..## .#..#..#.. ...#..#..# ....
output:
Red 9 Tie Black 50 Red 333 Red 41 Black 6 Red 133 Black 24 Red 111 Red 101
result:
ok 10 lines
Test #17:
score: 5
Accepted
time: 521ms
memory: 54216kb
input:
17 10 10 10 ########## .......... .......... ..######## .......... #########. .O........ .......... #......... O#X....... 10 10 .##...#... .#####..## ...#..##.# #........# #...#.#.#. ....#..... ..#####... ....#..#.. ..##O#.... .X...O##.# 10 10 #.......O. ..#....... ...##.##.. .......... .......... ....
output:
Black 60 Black 6 Red 53 Red 35 Tie Tie Red 9 Red 65 Tie Red 63
result:
ok 10 lines
Test #18:
score: 5
Accepted
time: 427ms
memory: 54232kb
input:
18 10 10 10 O......... #..#..###. .#.##...#. ..X....... .####..... .##...##.# ...#..###. ...###..O# ..#..#.... .......### 10 10 ...#.....O ........#. ........X. .......... ...#...... .......... .........# .....O.... ..#....... .......... 10 10 ..O.#..... #.#...#... ...#..###. ....#..... ..#..#..#. #...
output:
Red 159 Tie Red 73 Black 36 Black 56 Black 6 Red 15 Black 0 Red 63 Black 2
result:
ok 10 lines
Test #19:
score: 5
Accepted
time: 445ms
memory: 54208kb
input:
19 10 10 10 .....#.... ...#.#.#.# #..#.##.#. .##.....#. .#..##.#.# ...#...... #.#.#.##.. ##...#O##. ..#.#O.... .#...#..X. 10 10 .O....#... .####....# .###...#.. .......... ###....##. ....#..##. .#.#.#.... .##.O#..#. #..#...#.. ...#....X# 10 10 O######### #..#..#... ..#..#..## .#..#..#.. ...#..#..# ....
output:
Black 6 Red 57 Black 50 Red 11 Tie Red 129 Red 99 Black 0 Red 111 Red 27
result:
ok 10 lines
Test #20:
score: 5
Accepted
time: 436ms
memory: 54148kb
input:
20 10 10 10 .##.....## ...#....## .#.#...#.. .O###..... ###....... ......###. .....#..O. ##........ ..#...X... .##....... 10 10 #...#.##.. .O##.....# #.#.....#. .#...#.... ....#..#.. .###...... ....O##.#. .#.#.....# .......... .#.#...X#. 10 10 ......###. ..#.#..##. .#.......# .#.#..###. ..#.#..#.. #...
output:
Tie Red 63 Red 61 Red 9 Black 6 Black 0 Tie Red 333 Red 57 Tie
result:
ok 10 lines
Extra Test:
score: 0
Extra Test Passed