QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#509110	#6314. 过河卒	bribritt^#	15	2ms	4192kb	C++17	2.7kb	2024-08-08 10:24:22	2024-08-08 10:24:23

Judging History

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

[2024-08-08 10:24:23]
评测

测评结果：15
用时：2ms
内存：4192kb

查看

[2024-08-08 10:24:22]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i=0;i<n;i++)
main() {
  int id, T; cin >> id >> T; while(T--) {
    int n, m; cin >> n >> m;
    vector<string> s(n); for(int i=0;i<n;i++) cin>>s[i];
    vector<vector<int>> adjR(2*n*n*n*m*m*m);
    vector<int> dx={0,-1,0,1}, dy={1,0,-1,0};
    auto val = [n,m,&s](int bx, int by, int rx0, int ry0, int rx1, int ry1) {
      if(min({bx,by,rx0,ry0,rx1,ry1})<0||max({bx,rx0,rx1})>=n||max({by,ry0,ry1})>=m) return 0;
      if(s[bx][by]=='#'||s[rx0][ry0]=='#'||s[rx1][ry1]=='#') return 0;
      if(rx0==rx1&&ry0==ry1) return 0;
      return 1;
    };
    auto lost = [](int bx, int by, int rx0, int ry0, int rx1, int ry1) {
      if(!bx) return 1;
      if(bx==rx0&&by==ry0) return 1;
      if(bx==rx1&&by==ry1) return 1;
      return 0;
    };
    auto posId = [n,m](int bx, int by, int rx0, int ry0, int rx1, int ry1, bool redTurn) {
      return 2*(bx*n*n*m*m*m+by*n*n*m*m+rx0*n*m*m+ry0*n*m+rx1*m+ry1)+redTurn;
    };
    REP(bx,n) REP(by,m) REP(rx0,n) REP(ry0,m) REP(rx1,n) REP(ry1,m) if(val(bx,by,rx0,ry0,rx1,ry1)&&!lost(bx,by,rx0,ry0,rx1,ry1)) {
      REP(i,3) if(val(bx+dx[i],by+dy[i],rx0,ry0,rx1,ry1)) adjR[posId(bx+dx[i],by+dy[i],rx0,ry0,rx1,ry1,1)].push_back(posId(bx,by,rx0,ry0,rx1,ry1,0));
      REP(i,4) if(val(bx,by,rx0+dx[i],ry0+dy[i],rx1,ry1)) adjR[posId(bx,by,rx0+dx[i],ry0+dy[i],rx1,ry1,0)].push_back(posId(bx,by,rx0,ry0,rx1,ry1,1));
      REP(i,4) if(val(bx,by,rx0,ry0,rx1+dx[i],ry1+dy[i])) adjR[posId(bx,by,rx0,ry0,rx1+dx[i],ry1+dy[i],0)].push_back(posId(bx,by,rx0,ry0,rx1,ry1,1));
    }
    vector<int> deg(2*n*n*n*m*m*m,0);
    REP(i,2*n*n*n*m*m*m) for(auto j: adjR[i]) deg[j]++;
    stack<int> loss, win;
    vector<int> st(2*n*n*n*m*m*m,-1);
    REP(i,2*n*n*n*m*m*m) if(!deg[i]) loss.push(i), st[i]=-1e9;
    while(loss.size()||win.size()) {
      while(loss.size()) {
        int x = loss.top(); loss.pop();
        for(auto i: adjR[x]) if(st[i]<-1-st[x]) {
          st[i]=-1-st[x];
          win.push(i);
        }
      }
      while(win.size()) {
        int x = win.top(); win.pop();
        for(auto i: adjR[x]) {
          st[i] = max(st[i],1000000001-st[x]);
          deg[i]--;
          if(!deg[i] && st[i]<5e8) st[i]-=1e9, loss.push(i);
        }
      }
    }
    int bx, by, rx0=-1, ry0, rx1, ry1;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) {
      if(s[i][j]=='X') bx=i,by=j;
      if(s[i][j]=='O') {
        if(rx0==-1) rx0=i, ry0=j;
        else rx1=i, ry1=j;
      }
    }
    int ans = st[posId(bx,by,rx0,ry0,rx1,ry1,1)];
    if(ans<-1) cout<<"Black "<<ans+1e9<<"\n";
    else if(ans==-1) cout<<"Tie\n";
    else if(ans>5e8) cout<<"Red "<<1e9-ans<<"\n";
    else assert(0);
  }
}

源文件, 语言: C++17

詳細信息

Pretests

Final Tests

Test #1:

score: 0

Runtime Error

input:

1 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
4 1
O
O
#
X
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
#...

output:

result:

Test #2:

score: 0

Runtime Error

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

result:

Test #3:

score: 0

Runtime Error

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

result:

Test #4:

score: 0

Runtime Error

input:

4 10
10 10
.#......#.
..#....#..
#..#..#..#
..#.O..#..
.#......#.
...####...
##..X...##
..........
.##.O####.
..........
10 10
...#.##...
..####.##.
###.######
.####O#.X#
...####..#
.##O#..#.#
##.#..###.
#.#.#....#
.#.#####.#
.##.#.#.##
3 2
OO
##
#X
10 10
.##.##...#
..##..#.#O
.#O#.#...#
#.#.#..##.
...

output:

result:

Test #5:

score: 0

Time Limit Exceeded

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

result:

Test #6:

score: 0

Time Limit Exceeded

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

result:

Test #7:

score: 5

Accepted

time: 2ms

memory: 3924kb

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: 4192kb

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: 3848kb

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: 0

Runtime Error

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

result:

Test #11:

score: 0

Runtime Error

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

result:

Test #12:

score: 0

Runtime Error

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

result:

Test #13:

score: 0

Runtime Error

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

result:

Test #14:

score: 0

Runtime Error

input:

14 10
10 10
.......O..
..........
..........
O.........
..........
..........
..........
..........
.......X..
..........
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
....

output:

Red 27
Black 6

result:

Test #15:

score: 0

Runtime Error

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

result:

Test #16:

score: 0

Runtime Error

input:

16 10
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
.#..O...#.
...####...
##.X....##
..........
.#.O..#...
.#....#...
.#....#...
..####....
..........
..........
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:

Red 9

result:

Test #17:

score: 0

Runtime Error

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

result:

Test #18:

score: 0

Runtime Error

input:

18 10
10 10
O.........
#..#..###.
.#.##...#.
..X.......
.####.....
.##...##.#
...#..###.
...###..O#
..#..#....
.......###
10 10
...#.....O
........#.
........X.
..........
...#......
..........
.........#
.....O....
..#.......
..........
10 10
..O.#.....
#.#...#...
...#..###.
....#.....
..#..#..#.
#...

output:

Red 159

result:

Test #19:

score: 0

Runtime Error

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

result:

Test #20:

score: 0

Runtime Error

input:

20 10
10 10
.##.....##
...#....##
.#.#...#..
.O###.....
###.......
......###.
.....#..O.
##........
..#...X...
.##.......
10 10
#...#.##..
.O##.....#
#.#.....#.
.#...#....
....#..#..
.###......
....O##.#.
.#.#.....#
..........
.#.#...X#.
10 10
......###.
..#.#..##.
.#.......#
.#.#..###.
..#.#..#..
#...