結果

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

ソースコード

diff #
raw source code 

from collections import deque, defaultdict

def main():
    S = input().strip()
    visited = set()
    queue = deque([S])
    visited.add(S)
    
    while queue:
        current = queue.popleft()
        n = len(current)
        if n == 0:
            continue
        
        # Precompute prefix sums for 0 and 1
        pre0 = [0] * (n + 1)
        pre1 = [0] * (n + 1)
        for i in range(n):
            pre0[i+1] = pre0[i] + (current[i] == '0')
            pre1[i+1] = pre1[i] + (current[i] == '1')
        
        # Build a dictionary: (c0, c1) -> list of (i, j)
        subseq_dict = defaultdict(list)
        for i in range(n):
            for j in range(i, n):
                c0 = pre0[j+1] - pre0[i]
                c1 = pre1[j+1] - pre1[i]
                if c0 == 0 and c1 == 0:
                    continue  # since subseq must be non-empty
                subseq_dict[(c0, c1)].append( (i, j) )
        
        # For each (c0, c1) pair, process possible t and u pairs
        for key in subseq_dict:
            list_subseq = subseq_dict[key]
            m = len(list_subseq)
            # Sort the subseq list by their start index
            list_subseq.sort()
            # Enumerate all pairs t and u where t's end < u's start
            for a in range(m):
                i_a, j_a = list_subseq[a]
                # Use binary search to find the first subseq where start > j_a
                left = a + 1
                right = m
                while left < right:
                    mid = (left + right) // 2
                    i_b_mid, j_b_mid = list_subseq[mid]
                    if i_b_mid > j_a:
                        right = mid
                    else:
                        left = mid + 1
                # Now, left is the first index where i_b > j_a
                for b in range(left, m):
                    i_b, j_b = list_subseq[b]
                    # Check if the two subseqs are non-overlapping
                    if j_a < i_b:
                        # Generate new string by swapping t and u
                        part1 = current[:i_a]
                        part2 = current[i_b:j_b+1]
                        part3 = current[j_a+1:i_b]
                        part4 = current[i_a:j_a+1]
                        part5 = current[j_b+1:]
                        new_str = part1 + part2 + part3 + part4 + part5
                        if new_str not in visited:
                            visited.add(new_str)
                            queue.append(new_str)
    print(len(visited))

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