Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def create_graph(N, edge_pairs, is_bi_dir=False):
    in_vs, out_vs, weights = [], [], []
    for s, t, w in edge_pairs:
        in_vs.append(s)
        out_vs.append(t)
        weights.append(w)
        if is_bi_dir:
            in_vs.append(t)
            out_vs.append(s)
            weights.append(w)
    return csr_matrix((weights, (in_vs, out_vs)), shape=(N, N), dtype=np.int64)


N, M, L = map(int, input().split())
edge_pairs = []
for _ in range(M):
    s, t, w = map(int, input().split())
    edge_pairs.append((s-1, t-1, w))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph)
edge_pairs = []
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            edge_pairs.append((i, j, 1))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if np.isinf(ans):
        print(-1)
    else:
        print(int(ans - 1))


Fixed submission:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def create_graph(N, edge_pairs, is_bi_dir=False):
    in_vs, out_vs, weights = [], [], []
    for s, t, w in edge_pairs:
        in_vs.append(s)
        out_vs.append(t)
        weights.append(w)
        if is_bi_dir:
            in_vs.append(t)
            out_vs.append(s)
            weights.append(w)
    return csr_matrix((weights, (in_vs, out_vs)), shape=(N, N), dtype=np.int64)


N, M, L = map(int, input().split())
edge_pairs = []
for _ in range(M):
    s, t, w = map(int, input().split())
    edge_pairs.append((s-1, t-1, w))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph, directed=False)
edge_pairs = []
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            edge_pairs.append((i, j, 1))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph, directed=False)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if np.isinf(ans):
        print(-1)
    else:
        print(int(ans - 1))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(3 * 10 ** 5)


def main() -> None:
    def dfs(v, par, cnt):
        ans[v] = cnt + vs[v]
        for c in edges[v]:
            if c == par:
                continue
            dfs(c, v, ans[v])

    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edges[a].append(b)
        edges[b].append(a)
    vs = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        vs[p - 1] += x
    ans = [0] * N
    dfs(0, -1, 0)
    print(*ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(3 * 10 ** 5)
input = sys.stdin.buffer.readline


def main() -> None:
    def dfs(v, par, cnt):
        ans[v] = cnt + vs[v]
        for c in edges[v]:
            if c == par:
                continue
            dfs(c, v, ans[v])

    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edges[a].append(b)
        edges[b].append(a)
    vs = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        vs[p - 1] += x
    ans = [0] * N
    dfs(0, -1, 0)
    print(*ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
dp = [[0] * 13 for _ in range(2)]

mod = 10**9 + 7
dp[0][0] = 1
pow10 = 1
for i, s in enumerate(S[::-1]):
    now_idx, next_idx = i & 1, (i + 1) & 1
    dp[next_idx] = [0] * 13
    if s == '?':
        for j in range(13):
            for k in range(10):
                next_mod = (j + k * pow10) % 13
                dp[next_idx][next_mod] += dp[now_idx][j]
                dp[next_idx][next_mod] %= mod
    else:
        k = int(s)
        for j in range(13):
            next_mod = (j + k * pow10) % 13
            dp[next_idx][next_mod] += dp[now_idx][j]
            dp[next_idx][next_mod] %= mod
    pow10 = (pow10 * 10) % 13
print(dp[len(S) & 1][5])


Fixed submission:
S = input()
dp = [[0] * 13 for _ in range(2)]

mod = 10**9 + 7
dp[0][0] = 1
pow10 = 1
for i, s in enumerate(S[::-1]):
    now_idx, next_idx = i & 1, (i + 1) & 1
    dp[next_idx] = [0] * 13
    if s == '?':
        for j in range(13):
            for k in range(10):
                next_mod = (j + k * pow10) % 13
                dp[next_idx][next_mod] += dp[now_idx][j]
                dp[next_idx][next_mod] %= mod
    else:
        k = int(s)
        for j in range(13):
            next_mod = (j + k * pow10) % 13
            dp[next_idx][next_mod] += dp[now_idx][j]
            dp[next_idx][next_mod] %= mod
    pow10 = (pow10 * 10) % 13
print(dp[len(S) & 1][5])
Buggy python submission (verdict: Runtime Error):
N = int(input())
if N == 1:
    return 1
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)


Fixed submission:
N = int(input())
if N == 1:
    print(1)
    quit()
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)

Buggy python submission (verdict: Runtime Error):
N = int(input())
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)


Fixed submission:
N = int(input())
if N == 1:
    print(1)
    quit()
points = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
diff = dict()
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        x1, y1 = points[i]
        x2, y2 = points[j]
        pq = x1-x2, y1-y2
        diff[pq] = diff.get(pq, 0) + 1
val, key = max((v, k) for k, v in diff.items())
print(N-val)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt)
ans %= MOD
print(ans)


Fixed submission:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt, MOD) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt, MOD)
ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt)
ans %= MOD
print(ans)


Fixed submission:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt, MOD) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt, MOD)
ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt)
ans %= MOD
print(ans)


Fixed submission:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt, MOD) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt, MOD)
ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
M, K = map(int, input().split())

if M == 0:
    print(0, 0)
    quit()

if M == 1:
    if K == 0:
        print(0, 0, 1, 1)
    else:
        print(-1)
    quit()

if K >= (1 << M):
    print(-1)
    quit()


A = [i for i in range(1 << M) if i != K]
print(*A, K, *A[::-1], K)


Fixed submission:
import itertools
M, K = map(int, input().split())

if K >= (1 << M):
    print(-1)
    quit()

if M == 0:
    print(0, 0)
    quit()

if M == 1:
    if K == 0:
        print(0, 0, 1, 1)
    else:
        print(-1)
    quit()


A = [i for i in range(1 << M) if i != K]
print(*(A + [K] + A[::-1] + [K]))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N = int(input())
A = np.asarray([int(input()) for _ in range(N)], dtype=np.int64)

sum_A = A.sum()
MOD = 998244353

dp1 = np.zeros(sum_A + 1, dtype=np.int64)
dp2 = np.zeros(sum_A + 1, dtype=np.int64)
dp1[0] = dp2[0] = 1
tmp_sum = 0
for a in A:
    for i in reversed(range(tmp_sum + 1)):
        dp1[i] %= MOD
        dp2[i] %= MOD
        dp1[i + a] += dp1[i]
        dp1[i] <<= 1
        dp2[i + a] += dp2[i]
    tmp_sum += a


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)


Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] = (dp1_[i + a] + dp1[i]) % MOD
            dp2_[i + a] = (dp2_[i + a] + dp2[i]) % MOD
        # G, B に塗った場合
        dp1_[i] = (dp1_[i] + dp1[i] * 2) % MOD
        dp2_[i] = (dp2_[i] + dp2[i]) % MOD
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] += dp1[i]
            dp2_[i + a] += dp2[i]
        # G, B に塗った場合
        dp1_[i] += dp1[i] * 2
        dp2_[i] += dp2[i]
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans -= dp1[i] * 3
    if i * 2 == sum_A:
        ans += dp2[i] * 3
print(ans % MOD)


Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] = (dp1_[i + a] + dp1[i]) % MOD
            dp2_[i + a] = (dp2_[i + a] + dp2[i]) % MOD
        # G, B に塗った場合
        dp1_[i] = (dp1_[i] + dp1[i] * 2) % MOD
        dp2_[i] = (dp2_[i] + dp2[i]) % MOD
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A.sort()
B.sort()
if len(set(A)) != N or len(set(B)) != M:
    print(0)
    quit()
ans = 1
mod = 10 ** 9 + 7
for i in reversed(range(1, N * M + 1)):
    ai = bisect.bisect_left(A, i)
    bi = bisect.bisect_left(B, i)
    a_flag = A[ai] == i
    b_flag = B[bi] == i
    if a_flag and b_flag:
        pass
    elif a_flag:
        cand = M - bi
        ans = (ans * cand) % mod
    elif b_flag:
        cand = N - ai
        ans = (ans * cand) % mod
    else:
        cand = (N - ai) * (M - bi) - (N * M - i)
        if cand <= 0:
            print(0)
            quit()
        ans = (ans * cand) % mod
print(ans)


Fixed submission:
import bisect
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A.sort()
B.sort()
if len(set(A)) != N or len(set(B)) != M:
    print(0)
    quit()
if A[-1] != N * M or B[-1] != N * M:
    print(0)
    quit()
ans = 1
mod = 10 ** 9 + 7
for i in reversed(range(1, N * M + 1)):
    ai = bisect.bisect_left(A, i)
    bi = bisect.bisect_left(B, i)
    a_flag = A[ai] == i
    b_flag = B[bi] == i
    if a_flag and b_flag:
        pass
    elif a_flag:
        cand = M - bi
        ans = (ans * cand) % mod
    elif b_flag:
        cand = N - ai
        ans = (ans * cand) % mod
    else:
        cand = (N - ai) * (M - bi) - (N * M - i)
        if cand <= 0:
            print(0)
            quit()
        ans = (ans * cand) % mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2*10**5)

def rec(i, A, memo):
    if memo[i] != -1:
        return memo[i]

    for a in A:
        if i - a >= 0 and not rec(i - a, A, memo):
            memo[i] = True
            return True
    memo[i] = False
    return False


def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]
    memo = [-1] * (K + 1)
    print("First" if rec(K, A, memo) else "Second")


if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(2*10**5)

def rec(i, A, memo):
    if memo[i] != -1:
        return memo[i]

    for a in A:
        if i - a >= 0 and not rec(i - a, A, memo):
            memo[i] = True
            return True
    memo[i] = False
    return False


def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]
    memo = [-1] * (K + 1)
    print("First" if rec(K, A, memo) else "Second")


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2 * 10**5)
mod = 10 ** 9 + 7


def rec(v, p, color, graph, memo):
    if memo[v][color] != -1:
        return memo[v][color]
    ret = 1
    for c in graph[v]:
        if c == p:
            continue
        if color == 0:
            ret *= rec(c, v, 0, graph, memo) + rec(c, v, 1, graph, memo)
        else:
            ret *= rec(c, v, 0, graph, memo)
        ret %= mod
    memo[v][color] = ret
    return ret


def main():
    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        graph[x].append(y)
        graph[y].append(x)
    memo = [[-1, -1] for _ in range(N)]
    print((rec(0, -1, 0, graph, memo) + rec(0, -1, 1, graph, memo)) % mod)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(2 * 10**5)
mod = 10 ** 9 + 7


def rec(v, p, color, graph, memo):
    if memo[v][color] != -1:
        return memo[v][color]
    ret = 1
    for c in graph[v]:
        if c == p:
            continue
        if color == 0:
            ret *= rec(c, v, 0, graph, memo) + rec(c, v, 1, graph, memo)
        else:
            ret *= rec(c, v, 0, graph, memo)
        ret %= mod
    memo[v][color] = ret
    return ret


def main():
    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        graph[x].append(y)
        graph[y].append(x)
    memo = [[-1, -1] for _ in range(N)]
    print((rec(0, -1, 0, graph, memo) + rec(0, -1, 1, graph, memo)) % mod)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
points = [tuple(int(x) for x in input().split()) for _ in range(N)]
if any(abs(x + y) % 2 != abs(sum(points[0])) % 2 for x, y in points):
    print(-1)
    quit()
if any(not (-10 <= x <= 10 and -10 <= y <= 10) for x, y in points):
    assert False

M = 20 + (abs(sum(points[0])) % 2)
print(M)
print(*[1] * M)
for x, y in points:
    print("LR"[x > 0] * abs(x) + "DU"[y > 0] * abs(y) + "DU" * ((M - abs(x) - abs(y)) // 2))


Fixed submission:
N = int(input())
points = [tuple(int(x) for x in input().split()) for _ in range(N)]
if any(abs(x + y) % 2 != abs(sum(points[0])) % 2 for x, y in points):
    print(-1)
    quit()
even_flag = abs(sum(points[0])) % 2 == 0
points = [(x + y, x - y) for x, y in points]

M = 31 + even_flag
print(M)
print(*([1] if even_flag else []) + [1 << i for i in range(31)])
d_uv = {(0, 0): "L", (1, 1): "R", (1, 0): "U", (0, 1): "D"}
for u, v in points:
    ans = []
    if even_flag:
        ans.append("R")
        u, v = u - 1, v - 1
    sum_d_u = (u + (1 << 31) - 1) // 2
    sum_d_v = (v + (1 << 31) - 1) // 2
    for i in range(31):
        u_flag = sum_d_u >> i & 1
        v_flag = sum_d_v >> i & 1
        ans.append(d_uv[u_flag, v_flag])
    print(''.join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
def f(A, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
N = int(input())
A = [int(x) for x in input().split()]
left, right = -10**9, 10**9
while left + 2 < right:
    diff = (right - left) // 3
    m1 = left + diff
    m2 = m1 + diff
    if f(A, m1) > f(A, m2):
        left = m1
    else:
        right = m2
print(min(f(A, i) for i in range(left, right + 1)))


Fixed submission:
def f(A, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
N = int(input())
A = [int(x) for x in input().split()]
left, right = -10**9, 10**9
while left + 2 < right:
    diff = (right - left) // 3
    m1 = left + diff
    m2 = m1 + diff
    if f(A, m1) > f(A, m2):
        left = m1
    else:
        right = m2
print(min(f(A, i) for i in range(left, right + 1)))
Buggy python submission (verdict: Runtime Error):
S = input()
idx = 0
cnts = []
while idx < len(S):
    char = S[idx]
    cnt = 0
    while idx < len(S) and S[idx] == char:
        idx += 1
        cnt += 1
    cnts.append(cnt)
if len(cnts) <= 2:
    print(max(cnts))
    quit()
ans = (len(S) + 1) // 2
for i in range(len(cnts) - 2):
    ans = max(ans, min(cnts[i] + cnts[i + 1], cnts[i + 1] + cnts[i + 2]))
ans = max(ans, max(cnts))

flips = []
for i in range(len(cnts) - 1):
    flips.append((cnts[i] + cnts[i + 1], i))
flips.sort()

from bisect import bisect_left
left, right = (len(S) + 1) // 2, len(S)
while left + 1 < right:
    mid = (left + right) // 2
    _, mid_idx = flips[bisect_left(flips, (mid, -1))]
    ret = [False] * (len(cnts))
    for _, idx in flips[mid_idx:]:
        ret[idx] = ret[idx + 1] = True
    if all(x for x in ret):
        left = mid
    else:
        right = mid
ans = max(left, ans)
print(ans)


Fixed submission:
S = input()
if all(S[0] == x for x in S):
    print(len(S))
else:
    print(min(max(i + 1, len(S) - (i + 1)) for i in range(len(S) - 1) if S[i] != S[i + 1]))

Buggy python submission (verdict: Runtime Error):
S = input()
idx = 0
cnts = []
while idx < len(S):
    char = S[idx]
    cnt = 0
    while idx < len(S) and S[idx] == char:
        idx += 1
        cnt += 1
    cnts.append(cnt)
if len(cnts) <= 2:
    print(max(cnts))
    quit()
ans = (len(S) + 1) // 2
for i in range(len(cnts) - 2):
    ans = max(ans, min(cnts[i] + cnts[i + 1], cnts[i + 1] + cnts[i + 2]))
ans = max(ans, max(cnts))

flips = []
for i in range(len(cnts) - 1):
    flips.append((cnts[i] + cnts[i + 1], i))
flips.sort()

from bisect import bisect_left
left, right = (len(S) + 1) // 2, len(S)
while left + 1 < right:
    mid = (left + right) // 2
    _, mid_idx = bisect_left(flips, (mid, -1))
    ret = [False] * (len(cnts))
    for _, idx in flips[mid_idx:]:
        ret[idx] = ret[idx + 1] = True
    if all(x for x in ret):
        left = mid
    else:
        right = mid
ans = max(left, ans)
print(ans)


Fixed submission:
S = input()
if all(S[0] == x for x in S):
    print(len(S))
else:
    print(min(max(i + 1, len(S) - (i + 1)) for i in range(len(S) - 1) if S[i] != S[i + 1]))