QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104709#6314. 过河卒abcdefg100 ✓679ms54296kbC++177.4kb2023-05-11 19:09:442023-05-11 19:09:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 19:09:47]
  • 评测
  • 测评结果:100
  • 用时:679ms
  • 内存:54296kb
  • [2023-05-11 19:09:44]
  • 提交

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(); }

详细

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