QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325902#6314. 过河卒littlecat#100 ✓997ms63924kbC++143.8kb2024-02-12 03:58:372024-07-04 03:23:40

Judging History

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

  • [2024-07-04 03:23:40]
  • 评测
  • 测评结果:100
  • 用时:997ms
  • 内存:63924kb
  • [2024-02-12 03:58:37]
  • 提交

answer

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define pb push_back
using namespace std; 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; cin>>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; cin>>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]||b==a+1)&&(g[a+12]||b==a+12)
             &&g[b+12]&&g[b+1]&&(g[b-1]||a==b-1)&&(g[b-12]||a==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;
            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(dp[a][b][c][p]!=-1) continue;
            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));
            bad:;
        }
        test.clear(),T++;
    }
    int ans=dp[x1][x2][x3][0]; if(ans==-1) cout<<"Tie\n";
    else if(ans&1) cout<<"Red "<<ans<<'\n'; else cout<<"Black "<<ans<<'\n';
}
int main()
{
    int T; cin>>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: 5
Accepted
time: 424ms
memory: 51504kb

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: 347ms
memory: 51268kb

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: 357ms
memory: 51936kb

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: 215ms
memory: 32224kb

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: 735ms
memory: 53368kb

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: 661ms
memory: 53124kb

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: 4ms
memory: 22308kb

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: 0ms
memory: 22072kb

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

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: 470ms
memory: 52824kb

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: 563ms
memory: 63924kb

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: 588ms
memory: 60452kb

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: 595ms
memory: 60500kb

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: 997ms
memory: 61896kb

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: 336ms
memory: 41888kb

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: 356ms
memory: 40724kb

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: 614ms
memory: 54348kb

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: 402ms
memory: 50608kb

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: 427ms
memory: 53116kb

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: 369ms
memory: 38692kb

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