Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, R + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 重複組み合わせ
def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk - k, k)
    for i in range(k):
        value = (value * nk) % MOD
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, MOD - 2, MOD)) % MOD
    return value


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * nCr(K - 1, i - 1) % MOD)
    if i == K:
        print(nCr(R, i) % MOD)


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

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 2000 + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * nCr(K - 1, i - 1) % MOD)
    if i == K:
        print(nCr(R, i) % MOD)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, R + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 重複組み合わせ
def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk - k, k)
    for i in range(k):
        value = (value * nk) % MOD
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, MOD - 2, MOD)) % MOD
    return value


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * factorial[i] % MOD)
    if i == K:
        print(nCr(R, i) % MOD)


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

R = N - K + 1
# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 2000 + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


for i in range(1, K + 1):
    if i != K:
        print(nCr(R, i) * nCr(K - 1, i - 1) % MOD)
    if i == K:
        print(nCr(R, i) % MOD)
Buggy python submission (verdict: Runtime Error):
def main():
    H, W = map(int, raw_input().split())
    G = [list(raw_input()) for i in range(H)]


    up = [[0] * W for i in range(H)]  # あるマスから上に連続していくつ障害物のないマスが続くか
    right = [[0] * W for i in range(H)]  # あるマスから右に連続していくつ障害物のないマスが続くか
    down = [[0] * W for i in range(H)]  # あるマスから下に連続していくつ障害物のないマスが続くか
    left = [[0] * W for i in range(H)]  # あるマスから左に連続していくつ障害物のないマスが続くか


    # up
    for w in range(W):
        for h in range(1, H):
            if G[h - 1][w] == '#':
                continue
            up[h][w] = up[h - 1][w] + 1

    # right
    for h in range(H):
        for w in reversed(range(W - 1)):
            if G[h][w + 1] == '#':
                continue
            right[h][w] = right[h][w + 1] + 1

    # down
    for w in range(W):
        for h in reversed(range(H - 1)):
            if G[h + 1][w] == '#':
                continue
            down[h][w] = down[h + 1][w] + 1

    # left
    for h in range(H):
        for w in range(1, W):
            if G[h][w - 1] == '#':
                continue
            left[h][w] = left[h][w - 1] + 1


    ans = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == '#':
                continue
            ans = max(ans, up[h][w] + right[h][w] + down[h][w] + left[h][w] + 1)

    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]

# あるマスから（右・下・左・上）にいくつ障害物ないマスが続くか
right_space = [[-1] * (W + 2) for i in range(H + 2)]
down_space = [[-1] * (W + 2) for i in range(H + 2)]
left_space = [[-1] * (W + 2) for i in range(H + 2)]
up_space = [[-1] * (W + 2) for i in range(H + 2)]

# 左上から更新（上・左に対応）
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if G[h - 1][w - 1] == '.':
            up_space[h][w] = up_space[h - 1][w] + 1
            left_space[h][w] = left_space[h][w - 1] + 1

# 右下から更新（下・右に対応）
for h in reversed(range(1, H + 1)):
    for w in reversed(range(1, W + 1)):
        if G[h - 1][w - 1] == '.':
            down_space[h][w] = down_space[h + 1][w] + 1
            right_space[h][w] = right_space[h][w + 1] + 1

ans = 0
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if G[h - 1][w - 1] == '.':
            tmp_ans = right_space[h][w] + down_space[h][w] + left_space[h][w] + up_space[h][w] + 1
            ans = max(ans, tmp_ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())
S = input()

A, B, C, D = A - 1, B - 1, C - 1, D - 1
if (A < C < B < D) or (A < B < C < D):
    for i in range(A, C + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()
    for i in range(B, D + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()
    print('Yes')
    exit()

if A < B < D < C:
    for i in range(A, C + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()

    for i in range(B, D + 1):
        if S[i] == '#' and S[i + 1] == '#':
            print('No')
            exit()

    for i in range(B + 1, D + 1):
        if S[i] == '.' and S[i + 1] == '.' and S[i + 2] == '.':
            print('Yes')
            exit()
    print('No')


Fixed submission:
N, A, B, C, D = map(int, input().split())
S = input()

A, B, C, D = A - 1, B - 1, C - 1, D - 1
if (A < C < B < D) or (A < B < C < D):
    if '##' in S[A: C + 1]:
        print('No')
        exit()

    if '##' in S[B: D + 1]:
        print('No')
        exit()
    print('Yes')


if A < B < D < C:
    if '##' in S[A: C + 1]:
        print('No')
        exit()

    if '##' in S[B: D + 1]:
        print('No')
        exit()

    if '...' in S[B - 1: D + 2]:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Runtime Error):
import heapq

Q = int(input())
B = 0

q, a, b = map(int, input().split())
L, R = [-a], [a]
L_sum, R_sum = a, a
B = b

for i in range(Q - 1):
    q = list(map(int, input().split()))
    if len(q) == 3:
        A = q[1]
        B += q[2]

        if A <= -L[0]:
            heapq.heappush(L, -A)
            M = -heapq.heappushpop(L, -A)
            heapq.heappush(R, M)

            L_sum += (2 * A - M)
            R_sum += M
        else:
            heapq.heappush(R, A)
            M = heapq.heappush(R, A)
            heapq.heappush(L, -A)

            R_sum += (2 * A - M)
            L_sum += M
    else:
        N = len(L)
        X = -L[0]
        print(X, (abs(L_sum - X * N) + abs(R_sum - X * N)) // 2 + B)


Fixed submission:
import heapq
import sys

inp = sys.stdin.readline

Q = int(input())
B = 0

q, a, b = map(int, inp().split())
L, R = [-a], [a]
L_sum, R_sum = a, a
B = b

for i in range(Q - 1):
    q = list(map(int, inp().split()))
    if len(q) == 3:
        A = q[1]
        B += q[2]

        if A <= -L[0]:
            heapq.heappush(L, -A)
            M = -heapq.heappushpop(L, -A)
            heapq.heappush(R, M)

            L_sum += (2 * A - M)
            R_sum += M
        else:
            heapq.heappush(R, A)
            M = heapq.heappushpop(R, A)
            heapq.heappush(L, -M)

            R_sum += (2 * A - M)
            L_sum += M
    else:
        N = len(L)
        X = -L[0]
        print(X, (abs(L_sum - X * N) + abs(R_sum - X * N)) // 2 + B)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]


D = [[-1] * W for i in range(H)]
queue = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            queue.append([h, w])
            D[h][w] = 0


while queue:
    nh, nw = queue.pop()
    for dh, dw in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] >= 0:
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        queue.appendleft([nh + dh, nw + dw])


ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, D[h][w])

print(ans)


Fixed submission:
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]


D = [[-1] * W for i in range(H)]
queue = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            queue.append([h, w])
            D[h][w] = 0


while queue:
    nh, nw = queue.pop()
    for dh, dw in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] >= 0:
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        queue.appendleft([nh + dh, nw + dw])


ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, D[h][w])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)


AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])
AB.sort(reverse=True)
AB = AB[:K]

ans = []
for ab in AB:
    for c in C:
        ans.append(ab + c)

ans.sort(reverse=True)
print(*ans[:K], sep='\n')


Fixed submission:
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)


AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])
AB.sort(reverse=True)
AB = AB[:K]

ans = []
for ab in AB:
    for c in C:
        ans.append(ab + c)
        
ans.sort(reverse=True)
print(*ans[:K], sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
Query = [list(input().split()) for i in range(Q)]


# 番兵を設置
S = 'x' + S + 'x'

# 左から何番目のゴーレムまで消えるか二分探索
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    x = (ok + ng) // 2

    for t, d in Query:
        if S[x] != t:
            continue

        if d == 'R':
            x += 1
        if d == 'L':
            x -= 1

        if x == 0:
            ok = m
            break
    else:
        ng = m
Left_ans = ok

# 右から何番目のゴーレムまで消えるか二分探索
ok, ng = N + 1, 0
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    x = (ok + ng) // 2

    for t, d in Query:
        if S[x] != t:
            continue

        if d == 'R':
            x += 1
        if d == 'L':
            x -= 1

        if x == N + 1:
            ok = m
            break
    else:
        ng = m
Right_ans = ok

print(N - min(N, Left_ans + (N + 1 - Right_ans)))


Fixed submission:
N, Q = map(int, input().split())
S = input()
Query = [list(input().split()) for i in range(Q)]


# 番兵を設置
S = 'x' + S + 'x'

# 左から何番目のゴーレムまで消えるか二分探索
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    x = (ok + ng) // 2

    for t, d in Query:
        if S[x] != t:
            continue

        if d == 'R':
            x += 1
        if d == 'L':
            x -= 1

        if x == 0:
            ok = m
            break
    else:
        ng = m
Left_ans = ok

# 右から何番目のゴーレムまで消えるか二分探索
ok, ng = N + 1, 0
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    x = (ok + ng) // 2

    for t, d in Query:
        if S[x] != t:
            continue

        if d == 'R':
            x += 1
        if d == 'L':
            x -= 1

        if x == N + 1:
            ok = m
            break
    else:
        ng = m
Right_ans = ok

print(N - min(N, Left_ans + (N + 1 - Right_ans)))
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-float('inf')] + [int(input()) for _ in range(A)] + [float('inf')]
T = [-float('inf')] + [int(input()) for _ in range(B)] + [float('inf')]
S_rev = [-s for s in S][::-1]
T_rev = [-t for t in T][::-1]

for q in range(Q):
    x = int(input())
    ans = float('inf')

    # Case1: 右に直進
    cost1_s = S[bisect_left(S, x)] - x
    cost1_t = T[bisect_left(T, x)] - x
    ans = min(ans, max(cost1_s, cost1_t))

    # Case2: 左に直進
    cost2_s = S_rev[bisect_left(S_rev, -x)] + x
    cost2_t = T_rev[bisect_left(T_rev, -x)] + x
    ans = min(ans, max(cost2_s, cost2_t))

    # Case3: 右でS、左でT
    cost3_s = S[bisect_left(S, x)] - x
    cost3_t = T_rev[bisect_left(T_rev, -x)] + x
    ans = min(ans, 2 * min(cost3_s, cost3_t) + max(cost3_s, cost3_t))

    # Case4: 右でT、左でS
    cost3_s = S_rev[bisect_left(S_rev, -x)] + x
    cost3_t = T[bisect_left(T, x)] - x
    ans = min(ans, 2 * min(cost3_s, cost3_t) + max(cost3_s, cost3_t))

    print(ans)


Fixed submission:
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-float('inf')] + [int(input()) for i in range(A)] + [float('inf')]
T = [-float('inf')] + [int(input()) for i in range(B)] + [float('inf')]


for i in range(Q):
    x = int(input())
    Sx = bisect_left(S, x)
    Tx = bisect_left(T, x)
    S_w, S_e = S[Sx - 1], S[Sx]
    T_w, T_e = T[Tx - 1], T[Tx]

    S_wc, S_ec = abs(x - S_w), abs(x - S_e)
    T_wc, T_ec = abs(x - T_w), abs(x - T_e)

    west_only = max(S_wc, T_wc)
    east_only = max(S_ec, T_ec)
    west_east = 2 * min(S_wc, T_ec) + max(S_wc, T_ec)
    east_west = 2 * min(S_ec, T_wc) + max(S_ec, T_wc)

    print(min(west_only,
              east_only,
              west_east,
              east_west))
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


surplus = [(a - b) for a, b in zip(A, B) if (a - b) > 0]
surplus.sort(reverse=True)
surplus = [0] + list(accumulate(surplus))

short = [(b - a) for a, b in zip(A, B) if (b - a) > 0]
need = sum(short)
short_num = len(short)


if need > sum(surplus):
    print(-1)
    exit()
else:
    for i in range(N + 1):
        if surplus[i] >= need:
            print(i + short_num)
            exit()


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

A_origin = A[:]

if sum(A) < sum(B):
    print(-1)
    exit()

diff = [[i, a - b] for i, a, b in zip(range(N), A, B)]

order = sorted([[i, x] for i, x in diff if x > 0], key=lambda d: d[1])
C = []

charge = order.pop()
for i in range(N):
    while A[i] - B[i] < 0:
        if charge[1] > B[i] - A[i]:
            A[charge[0]] -= (B[i] - A[i])
            charge[1] -= (B[i] - A[i])
            A[i] = B[i]
        else:
            A[charge[0]] = B[charge[0]]
            A[i] += charge[1]
            charge = order.pop()

ans = 0
for a, ao in zip(A, A_origin):
    if a != ao:
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = raw_input()
    T = raw_input()
    
    # dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
    dp = [[''] * (len(T) + 1) for i in range(len(S) + 1)]
    
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            if S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + S[i - 1]
            else:
                if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i][j - 1]
    
    print(dp[-1][-1])
    
main()


Fixed submission:
S = input()
T = input()

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = ''
i, j = len(S), len(T)
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i, j = i - 1, j - 1
    elif dp[i][j - 1] > dp[i - 1][j]:
        j -= 1
    else:
        i -= 1

print(ans[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[''] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + S[i - 1]
        else:
            if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]

print(dp[-1][-1])


Fixed submission:
S = input()
T = input()

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = ''
i, j = len(S), len(T)
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i, j = i - 1, j - 1
    elif dp[i][j - 1] > dp[i - 1][j]:
        j -= 1
    else:
        i -= 1

print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


T = topological_sort(G)
dist = [0] * N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v], dist[n] + 1)

print(max(dist))


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


T = topological_sort(G)
dist = [0] * N
for n in T:
    for v in G[n]:
        dist[v] = max(dist[v], dist[n] + 1)

print(max(dist))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
acc = [0] + list(accumulate(A))

# dp[i][j] := 区間[i, j]のスライムたちを１匹にまとめるのに必要なコスト
dp = [[None] * N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(i, j):
    if j - i == 1:
        dp[i][j] = A[i] + A[j]
        return dp[i][j]

    if dp[i][j] is not None:
        return dp[i][j]

    ret = float('inf')
    for x in range(i, j):
        ret = min(ret, dfs(i, x) + dfs(x + 1, j) + acc[j + 1] - acc[i])

    dp[i][j] = ret
    return ret


print(dfs(0, N - 1))


Fixed submission:
import sys
from itertools import accumulate
sys.setrecursionlimit(10 ** 9)

N = int(input())
A = list(map(int, input().split()))
acc = [0] + list(accumulate(A))

# dp[i][j] := 区間[i, j]のスライムたちを１匹にまとめるのに必要なコスト
dp = [[None] * N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def dfs(i, j):
    if j - i == 1:
        dp[i][j] = A[i] + A[j]
        return dp[i][j]

    if dp[i][j] is not None:
        return dp[i][j]

    ret = float('inf')
    for x in range(i, j):
        ret = min(ret, dfs(i, x) + dfs(x + 1, j) + acc[j + 1] - acc[i])

    dp[i][j] = ret
    return ret


print(dfs(0, N - 1))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)

ans = 0
C = []
for x, num in dict(Counter(A)).items():
    C.append([x, num])
C.sort()

for i in range(N):
    for t in range(33, 0, -1):
        target = 2 ** t - A[i]
        if target < 0:
            continue
        target_t = bisect_left(C, [target, 0])

        if target_t >= N:
            continue

        x, num = C[target_t]
        if x == target and num > 0 and i != target_t:
            ans += 1
            C[i][1] -= 1
            C[target_t][1] -= 1
            break

print(ans)


Fixed submission:
from collections import Counter

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
C = Counter(A)
keys = set(A)

ans = 0
for a in A:
    target_2_pow = 2 ** a.bit_length()
    b = target_2_pow - a
    if b not in keys:
        continue

    if a != b:
        if C[a] == 0 or C[b] == 0:
            continue
    else:
        if C[b] < 2:
            continue
    ans += 1
    C[a] -= 1
    C[b] -= 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン(ただしレベル0バーガー参照時には+1)
        return 0 + (n == 0)

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで + (どうでもいい最後のバン)
    else:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)


print(solve(N, X))


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

a = [1]  # レベルiバーガーの長さ
p = [1]  # レベルiバーガーに含まれるパティの数
for i in range(N):
    a.append(2 * a[-1] + 3)
    p.append(2 * p[-1] + 1)


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1

    elif X <= 1 + a[N - 1]:
        return f(N - 1, X - 1)

    else:
        return p[N - 1] + 1 + f(N - 1, X - 2 - a[N - 1])


print(f(N, X))
Buggy python submission (verdict: Runtime Error):
from collections import deque
N = int(input())
A = deque(sorted([int(input()) for i in range(N)]))

X = deque([A.popleft()])
ans = 0
for i in range(N - 1):
    # Aのどちらから取り出してXのどちらに入れるか
    left_left = abs(X[0] - A[0])
    left_right = abs(X[-1] - A[0])
    right_left = abs(X[0] - A[-1])
    right_right = abs(X[-1] - A[-1])

    if left_left >= max(left_right, right_left, right_right):
        ans += left_left
        X.appendleft(A.popleft())

    elif left_right >= max(left_left, right_left, right_right):
        ans += left_right
        X.append(A.popleft())

    elif right_left >= max(left_left, left_right, right_right):
        ans += right_left
        X.appendleft(A.pop())

    else:
        ans += right_right
        X.appendleft(A.pop())

print(ans)


Fixed submission:
from itertools import combinations
N = int(input())


# kC2を満たすもののみ構築可能
creatable = []
for n in range(1, N + 1):
    num = n * (n + 1) // 2
    if num > N:
        break
    creatable.append(num)


# 構築不可能
if N not in creatable:
    print('No')
    exit()


# 部分集合の数
K = creatable.index(N) + 2
ans = [[] for i in range(K)]
for n, (c1, c2) in enumerate(combinations(range(K), 2), start=1):
    ans[c1].append(n)
    ans[c2].append(n)


# 出力
print('Yes')
print(K)
for a in ans:
    print(len(a), ' '.join(map(str, a)))