結果

問題 No.1694 ZerOne
ユーザー gew1fw
提出日時 2025-06-12 19:42:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,472 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 63,600 KB
最終ジャッジ日時 2025-06-12 19:43:02
合計ジャッジ時間 3,762 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def count_possible_strings(S):
    visited = set()
    queue = deque([S])
    visited.add(S)
    
    n = len(S)
    while queue:
        current = queue.popleft()
        # Precompute the number of 0s and 1s for all possible substrings
        # This is a 2D array where prefix[i][j] is the count of 0s from index i to j inclusive
        prefix = [[0]*(n) for _ in range(n)]
        for i in range(n):
            count0 = 0
            for j in range(i, n):
                if current[j] == '0':
                    count0 += 1
                prefix[i][j] = count0
        
        # Iterate over all possible t and u pairs
        for Lt in range(n):
            for Rt in range(Lt, n):
                t0 = prefix[Lt][Rt]
                t1 = (Rt - Lt + 1) - t0
                # Now find u after Rt
                for Lu in range(Rt+1, n):
                    for Ru in range(Lu, n):
                        u0 = prefix[Lu][Ru]
                        u1 = (Ru - Lu + 1) - u0
                        if t0 == u0 and t1 == u1:
                            # Swap t and u
                            new_str = current[:Lt] + current[Lu:Ru+1] + current[Rt+1:Lu] + current[Lt:Rt+1] + current[Ru+1:]
                            if new_str not in visited:
                                visited.add(new_str)
                                queue.append(new_str)
    return len(visited)

S = input().strip()
print(count_possible_strings(S))
0