結果

問題 No.2397 ω冪
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:10:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,646 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 855,884 KB
最終ジャッジ日時 2025-06-12 14:11:34
合計ジャッジ時間 4,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 3 MLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    n_bin = sys.stdin.readline().strip()
    m_bin = sys.stdin.readline().strip()

    memo = {}

    def get_decomposition(s):
        if s in memo:
            return memo[s]
        if s == '0':
            return (None, None)
        b = 0
        while len(s) > 0 and s[-1] == '0':
            b += 1
            s = s[:-1]
        if len(s) == 0:
            return (None, None)
        s_prime = s
        a_str = bin((int(s_prime, 2) - 1) // 2)[2:]
        memo[s] = (a_str, bin(b)[2:])
        return (a_str, bin(b)[2:])

    def build_tree(s):
        if s == '0':
            return None
        a_str, b_str = get_decomposition(s)
        a_tree = build_tree(a_str)
        b_tree = build_tree(b_str)
        return (a_tree, b_tree)

    n_tree = build_tree(n_bin)
    m_tree = build_tree(m_bin)

    def is_subtree(n_sub, m_sub):
        if n_sub is None and m_sub is None:
            return True
        if n_sub is None or m_sub is None:
            return False
        na, nb = n_sub
        ma, mb = m_sub
        if is_subtree(na, ma) and is_subtree(nb, mb):
            return True
        if is_subtree(na, ma) and is_subtree(nb, m_sub):
            return True
        if is_subtree(na, m_sub) and is_subtree(nb, ma):
            return True
        return False

    if n_bin == '0':
        if m_bin == '0':
            print("No")
            return
        else:
            print("Yes")
            return
    else:
        if is_subtree(n_tree, m_tree):
            print("Yes")
        else:
            print("No")

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