编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#101537 #1437. [L3-2] Ice World Time Limit Exceeded 70 32163 ms 243252 K Python 3 / 5.1 K wyhao 2024-03-13 1:19:07
N = 31
n = 0
a1 = 0
a2 = 0
b1 = 0
b2 = 0
c1 = 0
c2 = 0
d1 = 0
d2 = 0
dp = [[[[[[0 for _ in range(2)] for _ in range(4)] for _ in range(4)] for _ in range(N)] for _ in range(N)] for _ in range(2*N)]
vis = [[[[[[0 for _ in range(2)] for _ in range(4)] for _ in range(4)] for _ in range(N)] for _ in range(N)] for _ in range(2*N)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def cp1(x1,y1,xx,yy):
    global a1,b1,c1,d1
    if x1==a1 and y1==b1 and xx==c1 and yy==d1:
        return True
    if x1==c1 and y1==d1 and xx==a1 and yy==b1:
        return True
    return False
def cp2(x1,y1,xx,yy):
    global a2,b2,c2,d2
    if x1==a2 and y1==b2 and xx==c2 and yy==d2:
        return True
    if x1==c2 and y1==d2 and xx==a2 and yy==b2:
        return True
    return False
def chk(x1,y1,x2,y2,t1,t2):
    d = abs(x1-x2)+abs(y1-y2)
    if d<=1:
        if t1&1:
            return 1
        if t2&1:
            return -1
    if x1==x2 or y1==y2:
        if t1&2:
            return 1
        if t2&2:
            return -1
    return 0

def f(X,y1,y2,t1,t2,T):
    global vis,dp,dx,dy,n
    x1 = X+2-y1
    x2 = 2*n-X-y2+T
    # print(x1,y1,x2,y2)
    if vis[X][y1][y2][t1][t2][T]:
        return dp[X][y1][y2][t1][t2][T]
    # print(x1,y1,x2,y2,t1,t2)
    vis[X][y1][y2][t1][t2][T]=True
    if x1==n and y1==n and x2==1 and y2==1:
        dp[X][y1][y2][t1][t2][T]=0
        return 0
    t=1-T
    if t==1:
        ansk=-1
        for k in range(0,2):
            xx=x1+dx[k]
            yy=y1+dy[k]
            if xx<1 or xx>n or yy<1 or yy>n:
                continue
            if ((t2&1)!=1) and cp1(x1,y1,xx,yy):
                d=chk(xx,yy,x2,y2,t1+1,t2)
                if d==1:
                    dp[X][y1][y2][t1][t2][T]=1
                    return 1
                elif d==-1:
                    continue
                d=f(X+1,yy,y2,t1+1,t2,1)
                if(d==1):
                    dp[X][y1][y2][t1][t2][T]=1
                    return 1
                ansk=max(ansk,d)
            if ((t2&2)!=2) and cp2(x1,y1,xx,yy):
                d=chk(xx,yy,x2,y2,t1+2,t2)
                if d==1:
                    dp[X][y1][y2][t1][t2][T]=1
                    return 1
                elif d==-1:
                    continue
                d=f(X+1,yy,y2,t1+2,t2,1)
                if(d==1):
                    dp[X][y1][y2][t1][t2][T]=1
                    return 1
                ansk=max(ansk,d)
            d=chk(xx,yy,x2,y2,t1,t2)
            if d==1:
                dp[X][y1][y2][t1][t2][T]=1
                return 1
            elif d==-1:
                continue
            d=f(X+1,yy,y2,t1,t2,1)
            if(d==1):
                dp[X][y1][y2][t1][t2][T]=1
                return 1
            ansk=max(ansk,d)
        dp[X][y1][y2][t1][t2][T]=ansk
        return ansk
    else:
        ansk=1
        for k in range(2,4):
            xx=x2+dx[k]
            yy=y2+dy[k]
            if(xx<1 or xx>n or yy<1 or yy>n):
                continue
            if((t1&1)!=1) and (cp1(x2,y2,xx,yy)):
                d=chk(x1,y1,xx,yy,t1,t2+1)
                if(d==-1):
                    dp[X][y1][y2][t1][t2][T]=-1
                    return -1
                elif(d==1):
                    continue
                d=f(X,y1,yy,t1,t2+1,0)
                if(d==-1):
                    dp[X][y1][y2][t1][t2][T]=-1
                    return -1
                ansk=min(ansk,d)
            if((t1&2)!=2) and (cp2(x2,y2,xx,yy)):
                d=chk(x1,y1,xx,yy,t1,t2+2)
                if(d==-1):
                    dp[X][y1][y2][t1][t2][T]=-1
                    return -1
                elif(d==1):
                    continue
                d=f(X,y1,yy,t1,t2+2,0)
                if(d==-1):
                    dp[X][y1][y2][t1][t2][T]=-1
                    return -1
                ansk=min(ansk,d)
            d=chk(x1,y1,xx,yy,t1,t2)
            if d==-1:
                dp[X][y1][y2][t1][t2][T]=-1
                return -1
            elif d==1:
                continue
            d=f(X,y1,yy,t1,t2,0)
            if(d==-1):
                dp[X][y1][y2][t1][t2][T]=-1
                return -1
            ansk=min(ansk,d)
        dp[X][y1][y2][t1][t2][T]=ansk
        return ansk



def main():
    tests = int(input())
    for i in range(tests):
        global n,a1,a2,b1,b2,c1,c2,d1,d2,vis
        str = input().split(" ")
        n=int(str[0])
        a1=int(str[1])
        b1=int(str[2])
        c1=int(str[3])
        d1=int(str[4])
        a2=int(str[5])
        b2=int(str[6])
        c2=int(str[7])
        d2=int(str[8])
        N=n+1
        for X in range(0,2*N):
            for y1 in range(0,N):
                for y2 in range(0,N):
                    for t1 in range(0,4):
                        for t2 in range(0,4):
                            for t in range(0,2):
                                vis[X][y1][y2][t1][t2][t]=0
        d = f(0,1,n,0,0,0)
        if d==1:
            print("Alice")
        elif d==-1:
            print("Bob")
        else:
            print("0")

main()
子任务 #1
Time Limit Exceeded
得分:70
测试点 #1
Accepted
得分:100
用时:2291 ms
内存:243164 KiB

输入文件(1.in

20
2 2 1 2 2 1 1 1 2
2 1 1 2 1 1 1 1 2
2 2 1 2 2 2 1 2 2
2 1 2 2 2 2 1 2 2
2 1 1 1 2 1 1 1 2
2 1 1 2
<262 bytes omitted>

答案文件(1.out

Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alic
<14 bytes omitted>

用户输出

Alice
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice
Alice

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:2398 ms
内存:243192 KiB

输入文件(2.in

20
5 5 3 5 4 2 4 3 4
5 2 3 3 3 2 2 2 3
4 2 1 2 2 3 4 4 4
6 1 2 1 3 1 2 2 2
6 5 1 5 2 6 5 6 6
4 4 3 4
<262 bytes omitted>

答案文件(2.out

Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice

用户输出

Bob
Alice
Bob
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:2344 ms
内存:243124 KiB

输入文件(3.in

20
3 1 3 2 3 1 2 1 3
6 6 2 6 3 5 4 5 5
4 4 2 4 3 1 2 2 2
3 1 3 2 3 2 2 3 2
3 2 2 3 2 1 3 2 3
5 4 1 5
<262 bytes omitted>

答案文件(3.out

Alice
Bob
Alice
0
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
0
Alice
Bob
Bob
Alice
Bob

用户输出

Alice
Bob
Alice
0
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Alice
Alice
0
Alice
Bob
Bob
Alice
Bob

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:2317 ms
内存:243148 KiB

输入文件(4.in

20
5 4 3 4 4 2 3 2 4
4 3 4 4 4 3 4 4 4
3 2 1 2 2 2 3 3 3
4 1 4 2 4 1 1 1 2
4 1 1 1 2 4 1 4 2
6 3 4 3
<262 bytes omitted>

答案文件(4.out

Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bo
<2 bytes omitted>

用户输出

Alice
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Bob
Alice
Alice
Bob
Alice
Alice
Alice
Bob
Bob

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:2389 ms
内存:243072 KiB

输入文件(5.in

20
3 2 2 3 2 1 1 1 2
6 5 5 5 6 1 5 2 5
3 2 3 3 3 2 1 3 1
5 1 3 1 4 2 3 2 4
5 2 3 3 3 2 5 3 5
4 1 2 1
<262 bytes omitted>

答案文件(5.out

Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
0
Alice
Alice
Bob
Alice

用户输出

Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Alice
Bob
Bob
0
Alice
Alice
Bob
Alice

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:2657 ms
内存:243100 KiB

输入文件(6.in

20
9 4 2 4 3 4 7 5 7
9 3 7 4 7 4 4 5 4
10 2 9 3 9 9 8 10 8
9 4 1 5 1 7 7 7 8
9 8 7 9 7 4 1 5 1
10 7 
<276 bytes omitted>

答案文件(6.out

Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
0
0
Alice
Alice
Alice
Bob

用户输出

Bob
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
Alice
Alice
Bob
Bob
Bob
0
0
Alice
Alice
Alice
Bob

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:2661 ms
内存:243108 KiB

输入文件(7.in

20
10 4 2 5 2 8 1 8 2
9 9 3 9 4 6 3 7 3
10 4 6 5 6 3 4 3 5
9 7 9 8 9 1 6 2 6
9 7 7 7 8 6 8 7 8
9 4 3
<274 bytes omitted>

答案文件(7.out

Alice
Bob
Alice
0
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice

用户输出

Alice
Bob
Alice
0
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Alice
Alice
Alice

系统信息

Exited with return code 0
测试点 #8
Time Limit Exceeded
得分:0
用时:5030 ms
内存:243252 KiB

输入文件(8.in

20
12 11 6 11 7 4 7 5 7
10 3 7 4 7 7 1 8 1
18 9 16 10 16 12 10 12 11
22 12 13 13 13 4 9 5 9
5 4 2 4 
<344 bytes omitted>

答案文件(8.out

Alice
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice

用户输出

Alice
Alice
Bob
Alice
Bob
Alice
Bob
Bob
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Alice
Bob
Alice
Bob
Alice
测试点 #9
Time Limit Exceeded
得分:0
用时:5021 ms
内存:243152 KiB

输入文件(9.in

20
5 3 2 4 2 4 2 4 3
6 5 3 5 4 3 2 4 2
5 4 5 5 5 4 1 5 1
8 5 6 5 7 7 5 7 6
21 3 4 3 5 18 21 19 21
15
<339 bytes omitted>

答案文件(9.out

Alice
0
Bob
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Alice
Alice

用户输出

Alice
0
Bob
Bob
Bob
Alice
Bob
Bob
Alice
Alice
Alice
Alice
Alice
Bob
Bob
Bob
Bob
Bob
Alice
Alice
测试点 #10
Time Limit Exceeded
得分:0
用时:5055 ms
内存:243232 KiB

输入文件(10.in

20
30 16 8 16 9 9 24 9 25
30 6 6 7 6 15 23 16 23
30 28 23 28 24 8 12 9 12
30 22 24 23 24 28 28 29 28
<399 bytes omitted>

答案文件(10.out

Bob
Bob
0
Bob
Alice
Bob
Bob
Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice
Bob
Bob
Alice
Alice
Bob

用户输出

Bob
Bob
0
Bob
Alice