编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#101534 #1437. [L3-2] Ice World Time Limit Exceeded 0 10319 ms 145244 K Python 3 / 4.9 K wyhao 2024-03-13 1:14:53
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(1)] for _ in range(1)] for _ in range(1)]
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
        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)]
        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
得分:0
测试点 #1
Time Limit Exceeded
得分:0
用时:1018 ms
内存:123200 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
测试点 #2
Time Limit Exceeded
得分:0
用时:1016 ms
内存:125768 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
测试点 #3
Time Limit Exceeded
得分:0
用时:1015 ms
内存:125216 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
测试点 #4
Time Limit Exceeded
得分:0
用时:1065 ms
内存:125808 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
测试点 #5
Time Limit Exceeded
得分:0
用时:1020 ms
内存:125380 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
测试点 #6
Time Limit Exceeded
得分:0
用时:1012 ms
内存:132408 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
测试点 #7
Time Limit Exceeded
得分:0
用时:1067 ms
内存:132504 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
测试点 #8
Time Limit Exceeded
得分:0
用时:1011 ms
内存:137352 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
测试点 #9
Time Limit Exceeded
得分:0
用时:1043 ms
内存:143920 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
测试点 #10
Time Limit Exceeded
得分:0
用时:1052 ms
内存:145244 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