結果

問題 No.1694 ZerOne
ユーザー lam6er
提出日時 2025-04-15 22:55:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,236 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 81,916 KB
実行使用メモリ 55,092 KB
最終ジャッジ日時 2025-04-15 22:56:46
合計ジャッジ時間 3,817 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    s = input().strip()
    visited = set()
    queue = deque()
    visited.add(s)
    queue.append(s)
    
    while queue:
        current = queue.popleft()
        n = len(current)
        # Precompute prefix sums for 0s and 1s
        prefix0 = [0] * (n + 1)
        prefix1 = [0] * (n + 1)
        for i in range(n):
            prefix0[i+1] = prefix0[i] + (current[i] == '0')
            prefix1[i+1] = prefix1[i] + (current[i] == '1')
        
        # Preprocess all possible substrings grouped by their length
        substrs_by_len = {}
        for k in range(1, n):  # k is the length of the substring
            substrs = []
            max_i = n - k  # since j = i + k -1 must be <n
            for i in range(max_i + 1):
                j = i + k - 1
                cnt0 = prefix0[j+1] - prefix0[i]
                cnt1 = prefix1[j+1] - prefix1[i]
                substrs.append( (i, j, cnt0, cnt1) )
            substrs_by_len[k] = substrs
        
        # Enumerate all possible swaps
        for k in substrs_by_len:
            substrs = substrs_by_len[k]
            # Group substrings by (count0, count1)
            groups = {}
            for i, j, c0, c1 in substrs:
                key = (c0, c1)
                if key not in groups:
                    groups[key] = []
                groups[key].append( (i, j) )
            # Process each group
            for key in groups:
                group = groups[key]
                # Sort by starting index
                group.sort()
                # Check all pairs in the group
                for t_idx in range(len(group)):
                    ti, tj = group[t_idx]
                    for u_idx in range(t_idx + 1, len(group)):
                        ui, uj = group[u_idx]
                        if tj < ui:
                            # Swap the two substrings
                            new_s = current[:ti] + current[ui:uj+1] + current[tj+1:ui] + current[ti:tj+1] + current[uj+1:]
                            if new_s not in visited:
                                visited.add(new_s)
                                queue.append(new_s)
    print(len(visited))

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