QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325898#6314. 过河卒littlecat#0 0ms0kbC++144.0kb2024-02-12 03:52:222024-07-04 03:23:38

Judging History

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

  • [2024-07-04 03:23:38]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-02-12 03:52:22]
  • 提交

answer

#pragma GCC optimize("O3")
#include <fstream>
#include <vector>
#include <algorithm>
#include <tuple>
#define pb push_back
using namespace std; ifstream fin; ofstream fout; typedef tuple<int,int,int,bool> state;
bool g[144]; int dp[144][144][144][2];
void solve()
{
    int n,m,x1=0,x2=0,x3=0; fin>>n>>m; for(int i=1; i<=m+1; i++) g[(n+1)*12+i]=1; vector<int> cells;
    for(int i=1; i<=n; g[i*12+m+1]=1, i++) for(int j=i*12+1; j<=i*12+m; j++)
    {char c; fin>>c, g[j]=c=='#'; if(!g[j]) cells.pb(j); if(c=='X') x3=j; else if(c=='O') (x1?x2:x1)=j;}
    //-1: unknown, 0: player to move has lost, 1: win in 1 move
    for(int a:cells) for(int b:cells) if(a<b) for(int c:cells) dp[a][b][c][0]=dp[a][b][c][1]=-1;
    vector<state> prv, cur, test;
    for(int a:cells) for(int b:cells) if(a<b) for(int i=13; i<=m+12; i++) if(!g[i])
        dp[a][b][i][0]=0, prv.pb(state(a,b,i,0));
    for(int a:cells) for(int b:cells) if(a<b) for(int c:cells) if(c>24)
        if(a==c||b==c) dp[a][b][c][0]=dp[a][b][c][1]=0, prv.pb(state(a,b,c,0)),prv.pb(state(a,b,c,1));
        else
        {
            if(g[a-12]&&g[a-1]&&g[a+1]&&g[a+12]&&g[b-12]&&g[b-1]&&g[b+1]&&g[b+12])
                dp[a][b][c][0]=0, prv.pb(state(a,b,c,0));
            if(g[c-12]&&g[c-1]&&g[c+1]) dp[a][b][c][1]=0, prv.pb(state(a,b,c,1));
        }
    int T=1,a,b,c,p; while(!prv.empty())
    {
        //get states to update
        for(state s:prv)
        {
            tie(a,b,c,p)=s;
// fout<<"Expand  "<<a<<' '<<b<<' '<<c<<' '<<p<<'\n';
            if(p)
            {
                if(!g[a-12]) test.pb(state(a-12,b,c,0));
                if(!g[a-1]) test.pb(state(a-1,b,c,0));
                if(!g[b+12]) test.pb(state(a,b+12,c,0));
                if(!g[b+1]) test.pb(state(a,b+1,c,0));
                if(b!=a+12&&!g[a+12]) test.pb(state(min(a+12,b),max(a+12,b),c,0));
                if(b!=a+1&&!g[a+1]) test.pb(state(min(a+1,b),max(a+1,b),c,0));
                if(a!=b-12&&!g[b-12]) test.pb(state(min(a,b-12),max(a,b-12),c,0));
                if(a!=b-1&&!g[b-1]) test.pb(state(min(a,b-1),max(a,b-1),c,0));
            }
            else
            {
                if(!g[c-1]) test.pb(state(a,b,c-1,1));
                if(!g[c+12]) test.pb(state(a,b,c+12,1));
                if(!g[c+1]) test.pb(state(a,b,c+1,1));
            }
        }
        //compute
        prv.clear();
        for(state s:test)
        {
            tie(a,b,c,p)=s;
            if(a==c||b==c||c<24||dp[a][b][c][p]!=-1) continue;
// fout<<"Compute "<<a<<' '<<b<<' '<<c<<' '<<p<<'\n';
            vector<int> val;
            if(p)
            {
                if(!g[c-12]) val.pb(dp[a][b][c-12][0]);
                if(!g[c-1]) val.pb(dp[a][b][c-1][0]);
                if(!g[c+1]) val.pb(dp[a][b][c+1][0]);
            }
            else
            {
                if(!g[a-12]) val.pb(dp[a-12][b][c][1]);
                if(!g[a-1]) val.pb(dp[a-1][b][c][1]);
                if(!g[b+12]) val.pb(dp[a][b+12][c][1]);
                if(!g[b+1]) val.pb(dp[a][b+1][c][1]);
                if(b!=a+12&&!g[a+12]) val.pb(dp[min(a+12,b)][max(a+12,b)][c][1]);
                if(b!=a+1&&!g[a+1]) val.pb(dp[min(a+1,b)][max(a+1,b)][c][1]);
                if(a!=b-12&&!g[b-12]) val.pb(dp[min(a,b-12)][max(a,b-12)][c][1]);
                if(a!=b-1&&!g[b-1]) val.pb(dp[min(a,b-1)][max(a,b-1)][c][1]);
            }
            //win: min even + 1; lose: max odd + 1
            int ans=1e9; for(int t:val) if(!(t&1)) ans=min(ans,t+1);
            if(ans!=1e9) goto good;
            ans=0; for(int t:val) {ans=max(ans,t+1); if(t==-1) goto bad;}
            good: dp[a][b][c][p]=ans, prv.pb(state(a,b,c,p));
// fout<<"-> "<<ans<<'\n';
            bad:;
        }
        test.clear(),T++;
    }
    int ans=dp[x1][x2][x3][0]; if(ans==-1) fout<<"Tie\n";
    else if(ans&1) fout<<"Red "<<ans<<'\n'; else fout<<"Black "<<ans<<'\n';
}
int main()
{
    fin.open("zu.in"), fout.open("zu.out");
    int T; fin>>T>>T; for(int i=0; i<12; i++) g[i]=g[i*12]=1; while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

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
Dangerous Syscalls

input:

2 10
10 10
.#.####..#
.##..#####
##.###X###
#....####.
.#.#######
#.#O###.##
..##.####.
..########
##########
##O#.#.###
10 10
..#.###.##
......#..#
....#O....
#..#.....#
...#.#####
.....#..#.
..#.....#O
X#....###.
#.....##..
.#..##....
10 10
.......##.
.O##...##.
..#.......
####..O...
....#...##
.....

output:


result:


Test #3:

score: 0
Dangerous Syscalls

input:

3 10
10 10
##.#######
###..###OO
##X####.##
...#######
#..###...#
##...#####
##..#.####
..##..##.#
###..#.#.#
#.###..##.
10 10
.##..##...
.....##...
..X#.#....
#........#
..#.#.#...
.#...#.#..
#..#.#.#..
..#..#.#.#
...##O#...
..##O#.#..
10 10
..........
.X........
..........
..........
..#.......
.....

output:


result:


Test #4:

score: 0
Dangerous Syscalls

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
Dangerous Syscalls

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:


result:


Test #6:

score: 0
Dangerous Syscalls

input:

6 10
10 10
.....O....
..........
..........
..........
..........
.X........
..........
..........
##########
...O......
10 1
O
.
.
.
.
.
.
X
#
O
10 10
..........
..O.......
..........
..........
..........
X.........
..........
..........
##########
.......O..
10 10
..........
.....O....
.............

output:


result:


Test #7:

score: 0
Dangerous Syscalls

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:


result:


Test #8:

score: 0
Dangerous Syscalls

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:


result:


Test #9:

score: 0
Dangerous Syscalls

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:


result:


Test #10:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Test #11:

score: 0
Dangerous Syscalls

input:

11 10
10 10
...#.....#
..#.......
##.##.###.
##...#.##X
.....#...#
...#.#.O.#
..#...#...
.....#....
......#..#
#...#...O#
10 10
..###O#O#.
.#.###.##.
##..#..#..
....#X....
........##
........##
#...##....
...#..###.
........#.
..#...#.#.
10 10
######...#
O.X.O####.
#.#.#.#...
#.......#.
...##...#.
....

output:


result:


Test #12:

score: 0
Dangerous Syscalls

input:

12 10
10 10
##..##..O.
.#........
.#.......#
..........
#.........
.XO##.....
#.........
..........
..........
..........
5 6
#.####
#.####
#.OO##
#X####
######
10 10
....######
.#########
O...##.###
.#########
....######
####....#.
####.####.
####.O..#.
#######.#.
####....#X
10 10
..........
.........

output:


result:


Test #13:

score: 0
Dangerous Syscalls

input:

13 10
10 10
.##...#...
.#####..##
#..#..#..#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
.##......#
..#..##..O
...#.##...
##..#O..##
..#...#...
###.....#X
..#.......
.##.#.#...
.#.#.#..#.
#......#.#
10 10
.........#
..........
O.........
..........
....O.....
....

output:


result:


Test #14:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Test #15:

score: 0
Dangerous Syscalls

input:

15 10
10 10
.########O
.........#
########.#
.........#
.#########
..........
#########.
..........
.#########
.......O.X
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 8
####....
...#..#.
.###..#.
...#.O#.
##.#..#.
...####.
.##...

output:


result:


Test #16:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Test #17:

score: 0
Dangerous Syscalls

input:

17 10
10 10
##########
..........
..........
..########
..........
#########.
.O........
..........
#.........
O#X.......
10 10
.##...#...
.#####..##
...#..##.#
#........#
#...#.#.#.
....#.....
..#####...
....#..#..
..##O#....
.X...O##.#
10 10
#.......O.
..#.......
...##.##..
..........
..........
....

output:


result:


Test #18:

score: 0
Dangerous Syscalls

input:

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

output:


result:


Test #19:

score: 0
Dangerous Syscalls

input:

19 10
10 10
.....#....
...#.#.#.#
#..#.##.#.
.##.....#.
.#..##.#.#
...#......
#.#.#.##..
##...#O##.
..#.#O....
.#...#..X.
10 10
.O....#...
.####....#
.###...#..
..........
###....##.
....#..##.
.#.#.#....
.##.O#..#.
#..#...#..
...#....X#
10 10
O#########
#..#..#...
..#..#..##
.#..#..#..
...#..#..#
....

output:


result:


Test #20:

score: 0
Dangerous Syscalls

input:

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

output:


result: