結果
問題 | No.2814 Block Game |
ユーザー |
|
提出日時 | 2024-07-19 23:09:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 453 ms / 2,000 ms |
コード長 | 2,381 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 79,104 KB |
最終ジャッジ日時 | 2024-07-19 23:09:31 |
合計ジャッジ時間 | 11,911 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
import sysfrom itertools import permutationsfrom heapq import heappop,heappushfrom collections import dequeimport randomimport bisectinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())memo = {}def calc(a,b,c,d,which,goal,now):if (a,b,c,d,which,goal,now) in memo:return memo[a,b,c,d,which,goal,now]assert a+b == c+dif a+b == 0:if now == goal:return "Alice"else:return "Bob"res = "Alice" if which == "Bob" else "Bob"nxt = "Alice" if which == "Bob" else "Bob"if a and c and calc(a-1,b,c-1,d,nxt,goal,now^1) == which:res = whichif a and d and calc(a-1,b,c,d-1,nxt,goal,now) == which:res = whichif b and c and calc(a,b-1,c-1,d,nxt,goal,now) == which:res = whichif b and d and calc(a,b-1,c,d-1,nxt,goal,now) == which:res = whichmemo[a,b,c,d,which,goal,now] = resreturn resdef solve_even(N):p_cnt = 0for i in range(100):if (N-1)>>i & 1:p_cnt += 1check = N - (1<<p_cnt)if check == 0 or check & 1 == 1:return "Alice"else:return "Bob"def solve_odd(N):p_cnt = 0for i in range(100):if (N-1)>>i & 1:p_cnt += 1check = N - (1<<p_cnt)if check & 1 == 1:return "Alice"else:return "Bob"def solve(N,S):if S == "Even":return solve_even(N)else:return solve_odd(N)def solve_brute(N,S):if S == "Even":p_cnt = 0for i in range(100):if (N-1)>>i & 1:p_cnt += 1a = 1<<p_cntb = N - ac = (N+1)//2d = N - creturn calc(a,b,c,d,"Alice",0,0)else:p_cnt = 0for i in range(100):if (N-1)>>i & 1:p_cnt += 1a = 1<<p_cntb = N - ac = (N+1)//2d = N - creturn calc(a,b,c,d,"Alice",1,0)#for N in range(3,100):#for S in ["Even","Odd"]:#print(N,S)#assert solve(N,S) == solve_brute(N,S)for _ in range(int(input())):N,S = input().split()N = int(N)if N <= 2:print(solve_brute(N,S))else:print(solve(N,S))#print(solve(N,S),solve_brute(N,S))