結果

問題 No.2398 ヒドラ崩し
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:44:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,381 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,148 KB
実行使用メモリ 152,560 KB
最終ジャッジ日時 2025-04-16 15:47:11
合計ジャッジ時間 7,410 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 10 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def split_outer(s):
    parts = []
    depth = 0
    start = 0
    for i, c in enumerate(s):
        if c == '(':
            if depth == 0:
                start = i
            depth += 1
        else:
            depth -= 1
            if depth == 0:
                parts.append(s[start+1:i])
    return parts

def compute_grundy(s):
    memo = {}
    stack = [(s, False)]
    while stack:
        current, processed = stack.pop()
        if current in memo:
            continue
        if not processed:
            parts = split_outer(current)
            all_processed = True
            for part in parts:
                if part not in memo:
                    all_processed = False
                    break
            if all_processed:
                res = 0
                for part in parts:
                    res ^= (memo[part] + 1)
                memo[current] = res
            else:
                stack.append((current, True))
                for part in reversed(parts):
                    if part not in memo:
                        stack.append((part, False))
        else:
            parts = split_outer(current)
            res = 0
            for part in parts:
                res ^= (memo[part] + 1)
            memo[current] = res
    return memo.get(s, 0)

H = input().strip()
grundy_val = compute_grundy(H)
print(0 if grundy_val != 0 else 1)
0