QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #624079 | #6314. 过河卒 | propane | 100 ✓ | 1209ms | 36924kb | C++20 | 7.7kb | 2024-10-09 14:54:26 | 2024-10-09 14:54:27 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<set>
#include<cassert>
using namespace std;
using LL = long long;
const int dx[4]{0, 0, 1, -1};
const int dy[4]{-1, 1, 0, 0};
const int maxn = 2e6 + 5;
int f[maxn], din[maxn], val[maxn];
bool bad[maxn];
char s[12][12];
int q[maxn];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int _, T;
cin >> _ >> T;
while(T--){
int n, m;
cin >> n >> m;
int a = -1, b = -1, c = -1;
for(int i = 0; i < n; i++){
cin >> s[i];
for(int j = 0; j < m; j++){
if (s[i][j] == 'X') a = i * m + j;
if (s[i][j] == 'O'){
if (b == -1) b = i * m + j;
else c = i * m + j;
}
}
}
const int B = n * m;
auto get = [&](int x, int y, int z, int t){
return x * B * B + y * B + z + t * (B * B * B);
};
auto h = [&](int i){
auto [t, t1] = div(i, B * B * B);
auto [x, t2] = div(t1, B * B);
auto [y, z] = div(t2, B);
return array<int, 4>{x, y, z, t};
};
for(int i = 0; i < 2 * B * B * B; i++){
bad[i] = false;
din[i] = 0;
val[i] = 0;
f[i] = -1;
}
auto check = [&](int i){
auto [x, y] = div(i, m);
return x >= 0 and x < n and y >= 0 and y < m and s[x][y] != '#';
};
int hh = 0, tt = -1;
for(int i = 0; i < n * m; i++){
for(int j = 0; j < n * m; j++){
for(int k = 0; k < n * m; k++){
bool flag = false;
if (!check(i) or !check(j) or !check(k)) flag = true;
if (i == j and j == k) flag = true;
if (j == k) flag = true;
if (flag){
bad[get(i, j, k, 0)] = bad[get(i, j, k, 1)] = true;
}
else{
if (i / m == 0){
bad[get(i, j, k, 1)] = true;
}
}
for(int t = 0; t < 2; t++){
int id = get(i, j, k, t);
if (bad[id]) continue;
if (i == j or i == k){
f[id] = 0;
q[++tt] = id;
}
else if (i / m == 0 and t == 0){
f[id] = 0;
q[++tt] = id;
}
}
}
}
}
for(int p = 0; p < 2 * B * B * B; p++){
if (bad[p]) continue;
auto [i, j, k, t] = h(p);
if (t == 0){
auto [x, y] = div(i, m);
for(int u = 0; u < 3; u++){
int nx = x + dx[u];
int ny = y + dy[u];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
int id = get(nx * m + ny, j, k, t ^ 1);
if (bad[id]) continue;
din[id] += 1;
}
}
else{
{
auto [x, y] = div(j, m);
for(int u = 0; u < 4; u++){
int nx = x + dx[u];
int ny = y + dy[u];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
int id = get(i, nx * m + ny, k, t ^ 1);
if (bad[id]) continue;
din[id] += 1;
}
}
{
auto [x, y] = div(k, m);
for(int u = 0; u < 4; u++){
int nx = x + dx[u];
int ny = y + dy[u];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
int id = get(i, j, nx * m + ny, t ^ 1);
if (bad[id]) continue;
din[id] += 1;
}
}
}
}
for(int id = 0; id < 2 * B * B * B; id++){
if (bad[id]) continue;
if (f[id] == -1 and din[id] == 0){
f[id] = 0;
q[++tt] = id;
}
}
while(hh <= tt){
auto head = q[hh++];
auto [i, j, k, t] = h(head);
int cur = f[head];
if (t == 0){
auto [x, y] = div(i, m);
for(int u = 0; u < 3; u++){
int nx = x + dx[u];
int ny = y + dy[u];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
int id = get(nx * m + ny, j, k, t ^ 1);
if (bad[id]) continue;
--din[id];
if (cur == 0 and f[id] == -1){
f[id] = 1;
val[id] = val[head] + 1;
q[++tt] = id;
}
if (din[id] == 0 and f[id] == -1){
f[id] = 0;
val[id] = val[head] + 1;
q[++tt] = id;
}
}
}
else{
{
auto [x, y] = div(j, m);
for(int u = 0; u < 4; u++){
int nx = x + dx[u];
int ny = y + dy[u];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
int id = get(i, nx * m + ny, k, t ^ 1);
if (bad[id]) continue;
--din[id];
if (cur == 0 and f[id] == -1){
f[id] = 1;
val[id] = val[head] + 1;
q[++tt] = id;
}
if (din[id] == 0 and f[id] == -1){
f[id] = 0;
val[id] = val[head] + 1;
q[++tt] = id;
}
}
}
{
auto [x, y] = div(k, m);
for(int u = 0; u < 4; u++){
int nx = x + dx[u];
int ny = y + dy[u];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
int id = get(i, j, nx * m + ny, t ^ 1);
if (bad[id]) continue;
--din[id];
if (cur == 0 and f[id] == -1){
f[id] = 1;
val[id] = val[head] + 1;
q[++tt] = id;
}
if (din[id] == 0 and f[id] == -1){
f[id] = 0;
val[id] = val[head] + 1;
q[++tt] = id;
}
}
}
}
}
if (f[get(a, b, c, 0)] == -1) cout << "Tie" << '\n';
else{
if (f[get(a, b, c, 0)] == 0) cout << "Black" << ' ' << val[get(a, b, c, 0)] << '\n';
else cout << "Red" << ' ' << val[get(a, b, c, 0)] << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 733ms
memory: 36924kb
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: 599ms
memory: 36868kb
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: 630ms
memory: 36788kb
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: 479ms
memory: 32728kb
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: 871ms
memory: 36852kb
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: 782ms
memory: 36920kb
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: 2ms
memory: 11912kb
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: 2ms
memory: 11852kb
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: 0ms
memory: 11844kb
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: 766ms
memory: 36916kb
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: 865ms
memory: 36920kb
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: 796ms
memory: 36864kb
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: 841ms
memory: 36856kb
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: 1209ms
memory: 36856kb
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: 623ms
memory: 34816kb
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: 650ms
memory: 36876kb
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: 878ms
memory: 36860kb
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: 700ms
memory: 36804kb
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: 734ms
memory: 36788kb
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: 689ms
memory: 34824kb
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