結果

問題 No.1694 ZerOne
ユーザー gew1fw
提出日時 2025-06-12 14:44:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,481 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 108,080 KB
最終ジャッジ日時 2025-06-12 14:45:11
合計ジャッジ時間 3,919 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import deque

def count_distinct_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 substrings t and u
        for l_t in range(n):
            for r_t in range(l_t, n):
                cnt0_t = current[l_t:r_t+1].count('0')
                cnt1_t = (r_t - l_t + 1) - cnt0_t
                # Look for u after t
                for l_u in range(r_t + 1, n):
                    for r_u in range(l_u, n):
                        cnt0_u = current[l_u:r_u+1].count('0')
                        cnt1_u = (r_u - l_u + 1) - cnt0_u
                        if cnt0_t == cnt0_u and cnt1_t == cnt1_u:
                            # Swap t and u
                            # Extract the parts
                            before_t = current[:l_t]
                            t = current[l_t:r_t+1]
                            between = current[r_t+1:l_u]
                            u = current[l_u:r_u+1]
                            after_u = current[r_u+1:]
                            # Construct new string
                            new_str = before_t + u + between + t + after_u
                            if new_str not in visited:
                                visited.add(new_str)
                                queue.append(new_str)
    return len(visited)

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