結果

問題 No.765 ukuku 2
ユーザー qwewe
提出日時 2025-05-14 12:51:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,999 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 85,504 KB
最終ジャッジ日時 2025-05-14 12:52:49
合計ジャッジ時間 30,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    S = sys.stdin.readline().strip()
    n = len(S)
    if n == 0:
        print(0)
        return
    
    # Manacher's algorithm to find the longest palindrome substring
    def manachers(s):
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        max_len = 0
        max_center = 0
        for i in range(1, n-1):
            mirror = 2*C - i
            if i < R:
                P[i] = min(R - i, P[mirror])
            while T[i + P[i] + 1] == T[i - P[i] - 1]:
                P[i] += 1
            if i + P[i] > R:
                C, R = i, i + P[i]
            if P[i] > max_len:
                max_len = P[i]
                max_center = i
        start = (max_center - max_len) // 2
        end = start + max_len - 1
        return max_len, start, end
    
    L_manacher, a, b = manachers(S)
    original_L = L_manacher
    original_a = a
    original_b = b
    
    # Check if there's any character outside [a, b]
    has_outside = a > 0 or b < n - 1
    
    if has_outside:
        # Compute M, but the answer is max(original_L, M)
        pass
    else:
        # Compute M and take max(M, original_L -1)
        pass
    
    # Compute M using hash-based LCP
    MOD = 10**18 + 3
    BASE = 911382629
    
    # Precompute prefix hashes and powers for S and reversed S
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * BASE + ord(S[i])) % MOD
        power[i+1] = (power[i] * BASE) % MOD
    
    R = S[::-1]
    prefix_hash_r = [0] * (n + 1)
    for i in range(n):
        prefix_hash_r[i+1] = (prefix_hash_r[i] * BASE + ord(R[i])) % MOD
    
    def get_hash(prefix, power, l, r, mod):
        # return hash of s[l..r], 0-based
        res = (prefix[r+1] - prefix[l] * power[r - l + 1]) % mod
        return res
    
    M = 0
    for i in range(n):
        # Compute even case
        len_left = i
        len_right = n - i - 1
        max_possible = min(len_left, len_right)
        even_l = 0
        if max_possible > 0:
            low, high = 0, max_possible
            while low < high:
                mid = (low + high + 1) // 2
                start_r = n - i
                end_r = start_r + mid - 1
                start_s = i + 1
                end_s = i + 1 + mid - 1
                if end_r >= n or end_s >= n:
                    high = mid - 1
                    continue
                hash_r = get_hash(prefix_hash_r, power, start_r, end_r, MOD)
                hash_s = get_hash(prefix_hash, power, start_s, end_s, MOD)
                if hash_r == hash_s:
                    low = mid
                else:
                    high = mid - 1
            even_l = low
        even_length = 2 * even_l
        
        # Compute odd case
        len_right_odd = n - i - 2
        max_possible_odd = min(len_left, len_right_odd)
        odd_l = 0
        if len_right_odd >= 0 and max_possible_odd > 0:
            low, high = 0, max_possible_odd
            while low < high:
                mid = (low + high + 1) // 2
                start_r = n - i
                end_r = start_r + mid - 1
                start_s = i + 2
                end_s = i + 2 + mid - 1
                if end_r >= n or end_s >= n:
                    high = mid - 1
                    continue
                hash_r = get_hash(prefix_hash_r, power, start_r, end_r, MOD)
                hash_s = get_hash(prefix_hash, power, start_s, end_s, MOD)
                if hash_r == hash_s:
                    low = mid
                else:
                    high = mid - 1
            odd_l = low
        odd_length = 2 * odd_l + 1 if len_right_odd >= 0 else 0
        
        current_max = max(even_length, odd_length)
        if current_max > M:
            M = current_max
    
    if has_outside:
        print(max(original_L, M))
    else:
        print(max(M, original_L -1))
    
if __name__ == '__main__':
    main()
0