結果

問題 No.3068 Speedrun (Hard)
ユーザー flippergo
提出日時 2025-06-01 11:20:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 123 ms / 2,000 ms
コード長 2,277 bytes
コンパイル時間 633 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 75,512 KB
最終ジャッジ日時 2025-06-01 11:20:45
合計ジャッジ時間 3,811 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

A,B,C,D,N = map(int,input().split())
P,Q,R,S,T = map(int,input().split())
def ext_gcd(a,b):
    if b==0:
        return a,1,0
    d,x,y = ext_gcd(b,a%b)
    return d,y,x-(a//b)*y
def solve(a,b,c,A1,B1):
    if c<0:
        a = -a
        b = -b
        c = -c
    d,x,y = ext_gcd(a,b)
    if c%d!=0:
        return -1
    a //= d
    b //= d
    c //= d
    d,x,y = ext_gcd(a,b)
    x *= c
    y *= c
    if a>0 and b>0:
        low = max((-x+b-1)//b,(y-B1+a-1)//a)
        high = min((A1-x)//b,y//a)
    elif a>0 and b<0:
        low = max((A1-x+b-1)//b,(y-B1+a-1)//a)
        high = min(x1//(-b),y1//a)
    elif a<0 and b>0:
        low = max((-x+b-1)//b,(y+a-1)//a)
        high = min((A1-x)//b,(y-B1)//a)
    if low>high:
        return -1
    return (x,y,a,b,low,high)
ans = -1
if S==P and S==Q and S==R:
    x = min(A,N)
    y = min(B,N-x)
    z = min(C,N-x-y)
    w = N-x-y-z
    ans = (x,y,z,w)
elif S==P and S==Q and S!=R:
    z = (S*N-T)//(S-R)
    x = min(A,N-z)
    y = min(B,N-z-x)
    w = N-x-y-z
    ans = (x,y,z,w)
elif S==R and S!=P and S==Q:
    x = (S*N-T)//(S-P)
    y = min(A,N-x)
    z = min(C,N-x-y)
    w = N-x-y-z
    ans = (x,y,z,w)
elif S!=R and S!=P and S==Q:
    a = S-P
    b = S-R
    c = S*N-T
    x1,z1,a1,b1,low,high = solve(a,b,c,A,C)
    for k in range(low,high+1):
        x = x1+k*b1
        z = z1-k*a1
        y = min(B,N-x-z)
        w = N-x-y-z
        if 0<=w<=D:
            ans = (x,y,z,w)
            break
elif S==R and S!=Q and S==P:
    y = (S*N-T)//(S-Q)
    x = min(A,N-y)
    z = min(C,N-x-y)
    w = N-x-y-z
    ans = (x,y,z,w)
elif S!=R and S!=Q and S==P:
    a = S-Q
    b = S-R
    c = S*N-T
    y1,z1,a1,b1,low,high = solve(a,b,c,B,C)
    for k in range(low,high+1):
        y = y1+k*b1
        z = z1-k*a1
        x = min(A,N-y-z)
        w = N-x-y-z
        if 0<=w<=D:
            ans = (x,y,z,w)
            break
else:
    for z in range(C+1):
        a = S-P
        b = S-Q
        c = S*N-T-(S-R)*z
        if solve(a,b,c,A,B)==-1:continue
        x1,y1,a1,b1,low,high = solve(a,b,c,A,B)
        for k in range(low,high+1):
            x = x1+k*b1
            y = y1-k*a1
            w = N-x-y-z
            if 0<=w<=D:
                ans = (x,y,z,w)
                break
        if ans != -1:break
print(*ans)
0