結果

問題 No.3066 Collecting Coins Speedrun 1
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:00:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,618 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 93,256 KB
最終ジャッジ日時 2025-06-12 20:04:04
合計ジャッジ時間 3,348 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_grundy(max_l):
    grundy = [0] * (max_l + 1)
    grundy[0] = 0
    grundy[1] = 1
    grundy[2] = 0
    for l in range(3, max_l + 1):
        s = set()
        # Type 2 moves
        for a in range(0, l - 1):
            b = l - 2 - a
            if b < 0:
                continue
            s.add(grundy[a] ^ grundy[b])
        mex = 0
        while mex in s:
            mex += 1
        grundy[l] = mex
    return grundy

# Precompute grundy numbers up to a certain limit
max_grundy = 100  # Adjust based on observed patterns
grundy = compute_grundy(max_grundy)

# Function to compute g(L)
def g(L):
    if L <= max_grundy:
        return grundy[L]
    # Assume a pattern or periodicity beyond precomputed values
    # For example, beyond L=100, g(L) cycles with a certain period
    # This is a placeholder; actual pattern needs to be determined
    # For the sake of this example, returning 0 for L beyond precomputed
    return 0

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    A.sort()
    
    # Compute empty segments
    segments = []
    prev = 0
    for a in A:
        if a > prev + 1:
            segments.append(a - prev - 1)
        prev = a
    if prev < K:
        segments.append(K - prev)
    
    # Compute XOR of grundy numbers
    xor = 0
    for L in segments:
        if L == 0:
            continue
        xor ^= g(L)
    
    if xor != 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()
0