結果

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

ソースコード

diff #
raw source code 

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()
        # Generate all possible pairs of non-overlapping intervals t and u
        intervals = []
        # Precompute all possible intervals and their counts
        for i in range(n):
            for j in range(i, n):
                cnt0 = current[i:j+1].count('0')
                cnt1 = (j+1 - i) - cnt0
                intervals.append((i, j, cnt0, cnt1))
        # Check all pairs of intervals
        for idx1 in range(len(intervals)):
            i1, j1, c0_1, c1_1 = intervals[idx1]
            for idx2 in range(idx1 + 1, len(intervals)):
                i2, j2, c0_2, c1_2 = intervals[idx2]
                # Check if intervals are non-overlapping and have the same counts
                if (j1 < i2 or j2 < i1) and (c0_1 == c0_2 and c1_1 == c1_2):
                    # Ensure t is before u
                    if j1 < i2:
                        t_start, t_end = i1, j1
                        u_start, u_end = i2, j2
                    elif j2 < i1:
                        t_start, t_end = i2, j2
                        u_start, u_end = i1, j1
                    else:
                        continue  # overlapping
                    # Create new string by swapping t and u
                    t_part = current[t_start:t_end+1]
                    u_part = current[u_start:u_end+1]
                    before_t = current[0:t_start]
                    between = current[t_end+1:u_start]
                    after_u = current[u_end+1:]
                    new_str = before_t + u_part + between + t_part + after_u
                    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