Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def judge(n, k, a_list_s, f_list_s, v):
    res = 0
    # print(v)
    for i in range(n):
        a_necessary = v // f_list_s[i]
        # print(a_necessary, a_list_s[i])
        if a_list_s[i] > a_necessary:
            res += a_list_s[i] - a_necessary
    if res > k:
        return False
    else:
        return True


def solve_e(n, k, a_list, f_list):

    if sum(a_list) <= k:
        return 0
    
    a_list_s = sorted(a_list)
    f_list_s = sorted(f_list, reverse=True)

    left = 0
    right = 10 ** 12

    while right - left > 1:
        middle = (left + right) // 2
        if judge(n, k, a_list_s, f_list_s, middle):
            right = middle
        else:
            left = middle
    return right


def main():
    # input
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    f_list = list(map(int, input().split()))
    res = solve_e(n, k, a_list, f_list)
    print(res)


def test():
    assert solve_e(3, 5, [4, 2, 1], [2, 3, 1]) == 2
    assert solve_e(3, 8, [4, 2, 1], [2, 3, 1]) == 0
    assert solve_e(
        11, 14, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2]) == 12


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


Fixed submission:
def judge(n, k, a_list_s, f_list_s, v):
    res = 0
    # print(v)
    for i in range(n):
        a_necessary = v // f_list_s[i]
        # print(a_necessary, a_list_s[i])
        if a_list_s[i] > a_necessary:
            res += a_list_s[i] - a_necessary
    if res > k:
        return False
    else:
        return True


def solve_e(n, k, a_list, f_list):

    if sum(a_list) <= k:
        return 0
    
    a_list_s = sorted(a_list)
    f_list_s = sorted(f_list, reverse=True)

    left = 0
    right = 10 ** 12

    while right - left > 1:
        middle = (left + right) // 2
        if judge(n, k, a_list_s, f_list_s, middle):
            right = middle
        else:
            left = middle
    return right


def main():
    # input
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    f_list = list(map(int, input().split()))
    res = solve_e(n, k, a_list, f_list)
    print(res)


def test():
    assert solve_e(3, 5, [4, 2, 1], [2, 3, 1]) == 2
    assert solve_e(3, 8, [4, 2, 1], [2, 3, 1]) == 0
    assert solve_e(
        11, 14, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2]) == 12


if __name__ == "__main__":
    test()
    main()
Buggy python submission (verdict: Runtime Error):
def main(s, t):
    s = list(input())
    t = list(input())
    assert len(s) == len(t)
    res = 0
    for i, ss in enumerate(s):
        if ss == t[i]:
            res += 1
    return res


if __name__ == "__main__":
    main()


Fixed submission:
def solve(s, t):
    assert len(s) == len(t)
    res = 0
    for i, ss in enumerate(s):
        if ss == t[i]:
            res += 1
    return res


if __name__ == "__main__":
    S = list(input())
    T = list(input())
    print(solve(S, T))
Buggy python submission (verdict: Runtime Error):
def main():
    a, b = map(int, input().split())
    # 1 + R * (A - 1) >= B
    print((b - 1 + a - 2) // (a - 1))


if __name__ == "__main__":
    main()


Fixed submission:
N = int(input())
A_list = list(map(int, input().split()))

print(1 / sum([1 / a for a in A_list]))
Buggy python submission (verdict: Runtime Error):
def solve_e(n, a_list):
    days = 0
    ind_list = [0] * n
    match_count = 0
    queue = list(range(n))
    stack = dict()
    while len(queue) > 0:
        days += 1
        new_queue = []
        for p in queue:
            if ind_list[p] < n - 1:
                q = a_list[p][ind_list[p]] - 1
                k = str(min(p, q)) + "_" + str(max(p, q))
                if k in stack.keys():
                    ind_list[p] += 1
                    ind_list[q] += 1
                    # print(days, p, q)
                    new_queue.append(p)
                    new_queue.append(q)
                    match_count += 1
                else:
                    stack[k] = 1
        queue = new_queue
    if match_count == n * (n - 1) // 2:
        return days - 1
    else:
        return -1


def test():
    n = 1000
    a_list = []
    for i in range(N):
        a_list.append(list(range(1, i + 1)) + list(range(i + 2, n + 1)))
    print(solve_e(n, a_list))


def main():
    n = int(input())
    a_list = []
    for _ in range(n):
        a_list.append(list(map(int, input().split())))
    print(solve_e(n, a_list))


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_right
from collections import defaultdict

s = list(input())
t = list(input())

L = len(s)
M = len(t)

ss = s * 2

ind_dict = defaultdict(list)
for i in range(2 * L):
    ind_dict[ss[i]].append(i)


def query_str(c, ind):
    if len(ind_dict[c]) == 0:
        return -1
    else:
        r = bisect_right(ind_dict[c], ind)
        return ind_dict[c][r]


res_total = 0
res = -1
for i in range(M):
    res = query_str(t[i], res)
    if res == -1:
        res_total = 0
        break
    if res >= L:
        res -= L
        res_total += L

if res == -1:
    print(-1)
else:
    print(res_total + res + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a_list = list(map(int, input().split()))

res = 'Yes'

a_dict = dict()

for a in a_list:
    if a not in a_dict.keys():
        a_dict[a] = 1
    else:
        a_dict[a] += 1

a_keys = list(a_dict.keys())
if len(a_keys) > 3:
    res = 'No'
elif len(a_keys) == 3:
    a, b, c = a_keys
    if a_dict[a] != a_dict[b]:
        res = 'No'
    if a_dict[a] != a_dict[c]:
        res = 'No'
    if a ^ b != c:
        res = 'No'
    if b ^ c != a:
        res = 'No'
    if c ^ a != b:
        res = 'No'
elif len(a_keys) == 2:
    a, b = a_keys
    if a_dict[a] == 2 * a_dict[b]:
        if b != 0:
            res = 'No'
    elif 2 * a_dict[a] == a_dict[b]:
        if a != 0:
            res = 'No'
    else:
        res = 'No'
else:
    a = a_keys[0]
    if a != 0:
        res = 'No'
print(res)


Fixed submission:
from collections import Counter

N = int(input())
a_list = list(map(int, input().split()))

res = 'Yes'

a_dict = Counter(a_list)


a_keys = list(a_dict.keys())
if len(a_keys) > 3:
    res = 'No'
elif len(a_keys) == 3:
    a, b, c = a_keys
    if a_dict[a] != a_dict[b]:
        res = 'No'
    if a_dict[a] != a_dict[c]:
        res = 'No'
    if a ^ b != c:
        res = 'No'
    if b ^ c != a:
        res = 'No'
    if c ^ a != b:
        res = 'No'
elif len(a_keys) == 2:
    a, b = a_keys
    if a_dict[a] == 2 * a_dict[b]:
        if b != 0:
            res = 'No'
    elif 2 * a_dict[a] == a_dict[b]:
        if a != 0:
            res = 'No'
    else:
        res = 'No'
else:
    a = a_keys[0]
    if a != 0:
        res = 'No'
print(res)
Buggy python submission (verdict: Runtime Error):
S = list(input())
S_cnt = dict()

for s in S:
  if s in S_cnt.keys():
    S_cnt[s] += 1
  else:
    S_cnt[s] = 1
    
res = 'Yes'
for s in S_dict.keys():
  if S_dict[s] != 2:
    res = 'No'
print(res)


Fixed submission:
S = list(input())
S_cnt = dict()

for s in S:
  if s in S_cnt.keys():
    S_cnt[s] += 1
  else:
    S_cnt[s] = 1
    
res = 'Yes'
for s in S_cnt.keys():
  if S_cnt[s] != 2:
    res = 'No'
print(res)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
LARGE = 10 ** 9 + 7

# SQRT
R = 1
while (R + 1) ** 2 < N:
    R += 1

square = False
if (R + 1) ** 2 == N:
    square = True


DP_S = [1] * R
DP_L = [1] * R
N_L = [1] * R
DP_M = 0
L = R
if square:
    DP_M = 1
    L += 1


for i in range(R, -1, 0):
    Q = N // i
    DP_L[i - 1] = Q - L
    N_L[i - 1] = Q - L
    L = Q

for _ in range(K - 1):
    S = 0
    L = sum(DP_L) + DP_M
    SS = sum(DP_S)
    for i in range(R):
        DP_L[i] = S * N_L[i] % LARGE
        DP_S[i] = L + SS % LARGE
        S = (S + DP_S[i]) % LARGE
        L = (L - DP_L[i]) % LARGE

        if square:
            DP_M = (DP_M + SS) % LARGE

print((sum(DP_L) + sum(DP_S) + DP_M) % LARGE)


Fixed submission:
N, K = map(int, input().split())
LARGE = 10 ** 9 + 7

# SQRT
R = 1
while (R + 1) ** 2 < N:
    R += 1

square = False
if (R + 1) ** 2 == N:
    square = True


DP_S = [1] * R
DP_L = [1] * R
N_L = [1] * R
DP_M = 0
L = R
if square:
    DP_M = 1
    L += 1


for i in range(R, 0, -1):
    Q = N // i
    DP_L[i - 1] = Q - L
    N_L[i - 1] = Q - L
    L = Q

for _ in range(K - 1):
    S = 0
    L = sum(DP_L) + DP_M
    SS = sum(DP_S)
    for i in range(R):
        S = (S + DP_S[i]) % LARGE
        DP_S[i] = (L + SS) % LARGE
        L = (L - DP_L[i]) % LARGE
        DP_L[i] = (S * N_L[i]) % LARGE

    if square:
        DP_M = (DP_M + SS) % LARGE

print((sum(DP_L) + sum(DP_S) + DP_M) % LARGE)
Buggy python submission (verdict: Runtime Error):
N = int(input())
a_list = list(map(int, input().split()))
LARGE = 10**9 + 7

bins = [0] * 20

zeros = 0
v_dict = dict()
v_dict[0] = dict()
v_all_dict = dict()

for i in range(N):
    a = a_list[i]
    b = 0
    for k in range(20):
        r = (a // (2**k)) % 2
        bins[k] = (bins[k] + r) % 2
        b += bins[k]*(2**k)
    if b == 0:
        for v in v_dict[zeros].keys():
            if v not in v_all_dict.keys():
                v_all_dict[v] = [zeros, v_dict[zeros][v] % LARGE, 1]
            else:
                z, c1, c2 = v_all_dict[v]
                v_all_dict[v][2] = (v_all_dict[v][2] + v_all_dict[v][1] * (zeros - z)) % LARGE
                v_all_dict[v][1] = (v_all_dict[v][1] + v_all_dict[v][2] * v_dict[zeros][v]) % LARGE
        zeros += 1
        v_dict[zeros] = dict()
    else:
        if b in v_dict[zeros].keys():
            v_dict[zeros][b] += 1
        else:
            v_dict[zeros][b] = 1

if b == 0:
    res = 0
    for v in v_all_dict.keys():
        res += v_all_dict[v][1] + v_all_dict[v][2] - 1
    res += 1
else:
    z, c1, c2 = v_all_dict[b]
    res = (v_all_dict[b][2] + v_all_dict[b][1] * (zeros - z)) % LARGE
    
print(res)


Fixed submission:
N = int(input())
a_list = list(map(int, input().split()))
LARGE = 10**9 + 7


# cumsum
b_list = [0] * N
b = 0

for i in range(N):
    a = a_list[i]
    b = a ^ b
    b_list[i] = b

v_all_dict = dict()
for b in b_list:
    v_all_dict[b] = [0, 0, 1]

zeros = 0



for i in range(N):

    b = b_list[i]

    t = v_all_dict[b][0]

    # new b
    if t < zeros:
        v_all_dict[b][2] = (v_all_dict[b][2] + v_all_dict[b][1] * (zeros - t)) % LARGE
        v_all_dict[b][0] = zeros

    # up
    v_all_dict[b][1] = (v_all_dict[b][1] + v_all_dict[b][2]) % LARGE

    # zeros
    if b == 0:
        zeros += 1

# res
if b_list[-1] == 0:
    res = 0
    for v in v_all_dict.keys():
        if v != 0:
            res = (res + v_all_dict[v][1]) % LARGE
        else:
            res = (res + 2 ** (zeros - 1) - 1) % LARGE
    res += 1

else:
    v = b_list[-1]
    res = v_all_dict[v][2]

print(res % LARGE)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


# Graph
G = dict()

for h in range(H):
    for w in range(W):
        G[h * W + w] = dict()

for h in range(H):
    for w in range(W):
        if w != 0:
            G[h * W + w][h * W + w - 1] = 1
        if w != W - 1:
            G[h * W + w][h * W + w + 1] = 1
        if h != 0:
            G[h * W + w][h * W + w - W] = 1
        if h != H - 1:
            G[h * W + w][h * W + w + W] = 1


queue = deque(black_cells)
d = [10000]*(H*W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Fixed submission:
from collections import deque

H, W = map(int, input().split())

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


# Graph
def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p-W)
    if h != H-1:
        q_list.append(p+W)
    if w != 0:
        q_list.append(p-1)
    if w != W-1:
        q_list.append(p+1)
    return q_list


queue = deque(black_cells)
d = [10000]*(H*W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))
Buggy python submission (verdict: Runtime Error):
# D
N = int(input())
a_list = [0]*N
for i in range(N):
    a_list[i] = int(input())

L = 90001
LARGE = 998244353

DP = np.zeros(L, dtype="int")
DP[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP[j] = (2*DP[j] + DP[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP[j] = (2*DP[j]) % LARGE

DP2 = np.zeros(L, dtype="int")
DP2[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP2[j] = (DP2[j] + DP2[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP2[j] = (DP2[j]) % LARGE
S = sum(a_list)
if S % 2 == 0:
    h = S // 2
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE) + 3*DP2[h]) % LARGE
else:
    h = S // 2 + 1
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE)) % LARGE
print(res)

Fixed submission:
# D
N = int(input())
a_list = [0]*N
for i in range(N):
    a_list[i] = int(input())

L = 90001
LARGE = 998244353

DP = [0]*L
DP[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP[j] = (2*DP[j] + DP[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP[j] = (2*DP[j]) % LARGE

DP2 = [0]*L
DP2[0] = 1
for i in range(N):
    for j in range(L-1, a_list[i]-1, -1):
        DP2[j] = (DP2[j] + DP2[j - a_list[i]]) % LARGE
    for j in range(a_list[i]-1, -1, -1):
        DP2[j] = (DP2[j]) % LARGE
S = sum(a_list)
if S % 2 == 0:
    h = S // 2
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE) + 3*DP2[h]) % LARGE
else:
    h = S // 2 + 1
    res = ((3**N % LARGE) - (3*sum(DP[(h):]) % LARGE)) % LARGE
print(res)
Buggy python submission (verdict: Runtime Error):
S = list(input())

res_10 = 0
res_01 = 0

for i in range(N):
    if i % 2 == 0:
        if S[i] == "0":
            res_10 += 1
        else:
            res_01 += 1
    else:
        if S[i] == "1":
            res_10 += 1
        else:
            res_01 += 1
print(min(res_10, res_01))

Fixed submission:
S = list(input())
 
res_10 = 0
res_01 = 0
 
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "0":
            res_10 += 1
        else:
            res_01 += 1
    else:
        if S[i] == "1":
            res_10 += 1
        else:
            res_01 += 1
print(min(res_10, res_01))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
S = list(input())

res = 0
left = 0
right = 0
# start
cnt = 0
for i in range(N-1):
    if S[i] == "0" and S[i+1] == "1":
        cnt += 1
    if cnt == K and S[i+1] == "0":
        right = i + 1
        break
    if i == N - 2:
        right = N
    
res = max(res, right - left)

while right < N:
    left += 1
    right += 1
    while left < N:
        if S[left] == "1" and S[left-1] == "0":
            break
        else:
            left += 1
    while right < N:
        if S[right] == "0" and S[right+1] == "1":
            break
        else:
            right += 1
    res = max(res, right - left)
    
print(res)

Fixed submission:
N, K = map(int, input().split())
S = list(input())

res = 0
left = 0
right = 0
# start
cnt = 0
for i in range(N-1):
    if S[i] == "0" and S[i+1] == "1":
        cnt += 1
    if cnt == K and S[i+1] == "0":
        right = i
        break
    if i == N - 2:
        right = N - 1
    
res = max(res, right - left + 1)

while right < N-1:
    left += 1
    right += 1
    while left < N:
        if S[left] == "1" and S[left-1] == "0":
            break
        else:
            left += 1
    while right < N - 1:
        if S[right] == "1" and S[right+1] == "0":
            break
        else:
            right += 1
    res = max(res, right - left + 1)
    
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# D
X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

AB_list = [0]*(X*Y)
for i in range(X):
    for j in range(Y):
        AB_list[i*Y+j] = A_list[i] + B_list[j]
AB_list_s = sorted(AB_list)
if len(AB_list_s) > 3000:
    AB_list_s = AB_list_s[-3000:]
W = len(AB_list_s)
ABC_list = [0]*(W*Z)
for i in range(W):
    for j in range(Z):
        ABC_list[i*Z+j] = AB_list_s[i] + C_list[j]
ABC_list_s = sorted(ABC_list)
for i in range(K):
    print(ABC_list_s[-(i+1)])

Fixed submission:
# D
X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

AB_list = [0]*(X*Y)
for i in range(X):
    for j in range(Y):
        AB_list[i*Y+j] = A_list[i] + B_list[j]
AB_list_s = sorted(AB_list)
if len(AB_list_s) > 3000:
    AB_list_s = AB_list_s[-3000:]
W = len(AB_list_s)
ABC_list = [0]*(W*Z)
for i in range(W):
    for j in range(Z):
        ABC_list[i*Z+j] = AB_list_s[i] + C_list[j]
ABC_list_s = sorted(ABC_list)
for i in range(K):
    print(ABC_list_s[-(i+1)])
Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())
res = 0
cnt = 0

for i in range(1, min(A, B)+1):
	if A % i == 0 and B % i == 0:
        cnt += 1
    if cnt == K:
	    res = i
        break
print(res)


Fixed submission:
A, B, K = map(int, input().split())
res = 0
cnt = 0
 
for i in range(min(A, B), 0, -1):
  if A % i == 0 and B % i == 0:
    cnt += 1
  if cnt == K:
    res = i
    break
print(res)
Buggy python submission (verdict: Runtime Error):
# D

# 10^12 < 2^40

def hard_log2(N):
    
    r = 1
    l = 0
    while N >= 2*r:
        r *= 2
        l += 1
    return r, l

def maximize_simple(r_list, K, N):
    if K == 0:
        return 0
    R = 0
    L, M = hard_log2(K)
    for i in range(M+1):
        R += max(r_list[i], N - r_list[i])*(2**i)
        
    return R

def maximize(r_list, K, N):
    
    if K == 0:
        return 0
    
    L, M = hard_log2(K)
    
    if r_list[M] >= N - r_list[M]:
        return maximize_simple(r_list, L-1, N)+r_list[M]*(2**M)
    else:
        R = 0
        m = M
        while 2**m > K-L:
            R += (N-r_list[m])*(2**m)
            m -= 1
        
        return max(maximize(r_list, K-L, N)+R, maximize_simple(r_list, L-1, N)+r_list[M]*(2**M))

def main_d(A_list, N, K):
    r_list = [0]*41
    for i in range(41):
        for A in A_list:
            if (A % 2**(i+1)) >= 2**i:
                r_list[i] += 1
    if K == 0:
        R = 0
        for i in range(41):
            R += r_list[i]*(2**i)
        return R
    L, M = hard_log2(K)
    R = 0
    for i in range(M+1, 41):
        R += r_list[i]*(2**i)
    return R + maximize(r_list, K, N)
    

if __name__ == "__main__":
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    res = main_d(A_list, N, K)

    
    print(res)

Fixed submission:
# A

def main(a, b):
    return a / b

if __name__ == "__main__":
    T, X = map(int, input().split())
    res = main(T, X)
    print(res)
Buggy python submission (verdict: Runtime Error):
# D
N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
q_list = [0]*Q
for i in range(Q):
    q_list[i] = int(input())

# precompute

# res
M = (N+1)//2
S1 = [0]*M
S2 = [0]*M

s1 = 0
s2 = 0
for i in range(M):
    s1 += A_list[N-1-i]
    S1[i] = s1
    s2 += A_list[N-1-2*i]
    S2[i] = s2

# bins
bins = [0]*(M-1)
for i in range(M-1):
    bins[i] = (A_list[N - (i+2)] + A_list[N - (2*i+3)]) / 2

# function for binary search
def bisearch(q):
    
    if q > bins[0]:
        return 0
    elif q <= bins[M-2]:
        return M - 1
    
    l = 0
    r = M - 2
    while l < r - 1:
        m = (l + r) // 2
        if q > bins[m]:
            r = m
        else:
            l = m
    return l+1
    
    

# first conflict
for q in q_list:
    r = bisearch(q)
    print(S1[r]+s2-S2[r])

Fixed submission:
# D
N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
q_list = [0]*Q
for i in range(Q):
    q_list[i] = int(input())

# precompute

# res
M = (N+1)//2
S1 = [0]*M
S2 = [0]*M

s1 = 0
s2 = 0
for i in range(M):
    s1 += A_list[N-1-i]
    S1[i] = s1
    s2 += A_list[N-1-2*i]
    S2[i] = s2

# bins
bins = [0]*(M-1)
for i in range(M-1):
    bins[i] = (A_list[N - (i+2)] + A_list[N - (2*i+3)]) / 2

# function for binary search
def bisearch(q):
    
    if q > bins[0]:
        return 0
    elif q <= bins[M-2]:
        return M - 1
    
    l = 0
    r = M - 2
    while l < r - 1:
        m = (l + r) // 2
        if q > bins[m]:
            r = m
        else:
            l = m
    return l+1
    
    
if N > 2:
    # first conflict
    for q in q_list:
        r = bisearch(q)
        print(S1[r]+s2-S2[r])
else:
    for q in q_list:
        print(A_list[1])
Buggy python submission (verdict: Time Limit Exceeded):
# B
N = int(input())
A_list = list(map(int, input().split()))

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    # partner
    r = 1
    while r < a:
        r *= 2
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)

Fixed submission:
# B
import math

N = int(input())
A_list = list(map(int, input().split()))

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    # partner
    r = 2**math.ceil(math.log2(a))
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# B
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
NN = N*(N+1) // 2

arr = [0] * NN
res = 0

# bruce
ind = 0
for i in range(N):
    r = 0
    for j in range(i, N):
        r += a_list[j]
        arr[ind] = r
        ind += 1
        
# get Greedy
for m in range(40, 0, -1):
    cnt = 0
    for i in range(NN):
        if (arr[i] // (2**m)) % 2 == 1:
            cnt += 1
    if cnt >= K:
        res += 2**m
        for i in range(NN):
            if (arr[i] // (2**m)) % 2 == 0:
                arr[i] = 0

print(res)

Fixed submission:
# B
N, K = map(int, input().split())
a_list = list(map(int, input().split()))
NN = N*(N+1) // 2

arr = [0] * NN
res = 0

# bruce
ind = 0
for i in range(N):
    r = 0
    for j in range(i, N):
        r += a_list[j]
        arr[ind] = r
        ind += 1
        
# get Greedy
for m in range(40, -1, -1):
    cnt = 0
    for i in range(NN):
        if (arr[i] // (2**m)) % 2 == 1:
            cnt += 1
    if cnt >= K:
        res += 2**m
        for i in range(NN):
            if (arr[i] // (2**m)) % 2 == 0:
                arr[i] = 0

print(res)