結果

問題 No.1694 ZerOne
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:30:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,254 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 292 ms
コンパイル使用メモリ 83,032 KB
実行使用メモリ 207,312 KB
最終ジャッジ日時 2025-03-20 20:31:53
合計ジャッジ時間 3,957 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def solve():
    from collections import deque
    S = input().strip()
    visited = {S}
    queue = deque([S])
    n = len(S)
    
    while queue:
        current = queue.popleft()
        # Precompute all possible substring's 0 and 1 counts
        t_list = []
        t_map = {}
        for Lt in range(n):
            for Rt in range(Lt, n):
                substring = current[Lt:Rt+1]
                cnt0 = substring.count('0')
                cnt1 = (Rt - Lt + 1) - cnt0
                key = (cnt0, cnt1)
                if key not in t_map:
                    t_map[key] = []
                t_map[key].append((Lt, Rt))
        # Now check for each possible t and find possible u's in the correct positions
        processed = set()
        for Lt in range(n):
            for Rt in range(Lt, n):
                cnt0_t = current[Lt:Rt+1].count('0')
                cnt1_t = (Rt - Lt + 1) - cnt0_t
                key = (cnt0_t, cnt1_t)
                # Look for u's with the same key and starting after Rt + 1
                if key not in t_map:
                    continue
                for Lu_start, Lu_end in t_map[key]:
                    if Lu_start > Rt:
                        # Check if this pair (Lt, Rt) and (Lu, Lv) is valid
                        # Ensure they are in the correct order and not overlapping
                        # Now generate the new string
                        # Split the current string into parts
                        part1 = current[:Lt]
                        part2 = current[Lu_start:Lu_end+1]
                        part3 = current[Rt+1:Lu_start]
                        part4 = current[Lt:Rt+1]
                        part5 = current[Lu_end+1:]
                        new_s = part1 + part2 + part3 + part4 + part5
                        if new_s not in visited:
                            visited.add(new_s)
                            queue.append(new_s)
        # Now handle pairs where t is after u, by iterating all possible u and then t
        # To avoid double processing, we check for the keys again but ensure u is before t
        # However, based on problem conditions, u must be after t, so the initial loop covers all possibilities
    
    print(len(visited))

solve()
0