Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math

A, B = map(int, input().split())
d = math.gcd(A, B)
#print('d={}'.format(d))

# make a prime list
# nまでの自然数が素数かどうかを表すリストを返す、エラストテネスの篩 O(nloglogn)
def make_prime_checker(n):
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime
 
primes = [p for p, is_prime in enumerate(make_prime_checker(10**6)) if is_prime]
 
ans = 1
for p in primes:
    if d % p == 0:
        ans += 1
        #print('p={}'.format(p))
    elif p > d:
        print(ans)
        exit()


Fixed submission:
import fractions

# divisor
def div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

def factor(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr

def main():
    A, B = map(int, input().split())
    d = fractions.gcd(A, B)
    #print('d={}'.format(d))

    if d == 1:
        print(1)
    else:
        print(1 + len(factor(d)))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

# 全ての部分集合の列挙
def subset_family(items, length):
    subsets = []
    for i in range(length + 1):
        for c in combinations(items, i):
            subsets.append(c)
    return subsets


N, M = map(int, input().split())

dp = [[float('inf')] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0
"""
dp[i][j] = (i + 1 番目以降の鍵は購入せずに状態を j にする為に必要な最小費用)
部分集合族はビットで管理すれば良い(0 <= j <= 2**N-1)
"""

for i in range(1, M + 1):
    dp[i] = dp[i - 1]
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(2 ** N):
        """
        DPは送る方向に考えるか受け取る方向に考えるかの２通りのやり方がある
        今回は受け取る方は難しいので送る方で考える
        またjは昇順に考えると偶然うまくDPの状態が順番に確定していく
        """
        for subset in subset_family(c, b):
            val = 0
            for num in subset:
                val += 2 ** (num - 1)

            if j | val < 2 ** N:
                dp[i][j | val] = min(dp[i - 1][j] + a, dp[i - 1][j | val])
    #print('dp[{}]={}'.format(i, dp[i]))

ans = dp[M][2 ** N - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from itertools import combinations

# 全ての部分集合の列挙
def subset_family(items, length):
    subsets = []
    for i in range(length + 1):
        for c in combinations(items, i):
            subsets.append(c)
    return subsets


N, M = map(int, input().split())

dp = [[float('inf')] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0
"""
dp[i][j] = (i + 1 番目以降の鍵は購入せずに状態を j にする為に必要な最小費用)
部分集合族はビットで管理すれば良い(0 <= j <= 2**N-1)
"""

for i in range(1, M + 1):
    dp[i] = dp[i - 1]
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(2 ** N):
        """
        DPは送る方向に考えるか受け取る方向に考えるかの２通りのやり方がある
        今回は受け取る方は難しいので送る方で考える
        またjは昇順に考えると偶然うまくDPの状態が順番に確定していく
        """
        """
        以下のようにcで開けられる箱の部分集合全てを考えても良いが、
        結局ほしいのはdp[M][2 ** N - 1]の右端の値なので、中間状態は吹っ飛ばして良い。
        for subset in subset_family(c, b):
            val = 0
            for num in subset:
                val += 2 ** (num - 1)

            if j | val < 2 ** N:
                dp[i][j | val] = min(dp[i - 1][j] + a, dp[i - 1][j | val])
        """
        val = 0
        for num in c:
            val += 2 ** (num - 1)
        dp[i][j | val] = min(dp[i - 1][j] + a, dp[i - 1][j | val])
    #print('dp[{}]={}'.format(i, dp[i]))

ans = dp[M][2 ** N - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()

if S = 'Sunny':
    print('Cloudy')
elif S = 'Cloudy':
    print('Rainy')
else:
    print('Sunny')

Fixed submission:
S = input()

if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
lst = [i for i in range(2, N + 1)] + [1]

val = 0
for i in range(N):
    val += (i + 1) % lst[i]

print(val)

Fixed submission:
N = int(input())
print(N * (N - 1) // 2)
Buggy python submission (verdict: Runtime Error):
import bisect

s = input()
t = input()
T = set(t)
s_num = len(s)
t_num = len(T)

# make a dictonary whose keys are the alphabets in t
dict = {}
appearing_times = {}

# when each alphabet in t appears in s
for w in T:
    dict[w] = []
    appearing_times[w] = 0
    index = -1
    while True:
        index = s.find(w, index + 1)
        if index == -1 and appearing_times[w] == 0:
            print(-1)
            exit()
        elif index == -1:
            break
        else:
            dict[w].append(index)
            appearing_times[w] += 1

# how many times s is repeated
count = 0
# 0 <= length <= s_num - 1
s_index = 0
check = 0

for w in t:
    idx = bisect.bisect_left(dict[w], s_index)
    if check == 'done' and s_index == dict[w][idx]:
        idx = idx + 1

    if idx < appearing_times[w]:
        s_index = dict[w][idx]
    else:
        count += 1
        s_index = dict[w][0]

    check = 'done'
print(count * s_num + s_index + 1)


Fixed submission:
import bisect

s = input()
t = input()
T = set(t)
s_num = len(s)
t_num = len(T)

# make a dictonary whose keys are the alphabets in t
dict = {}
appearing_times = {}

# when each alphabet in t appears in s
for w in T:
    dict[w] = []
    appearing_times[w] = 0
    index = -1
    while True:
        index = s.find(w, index + 1)
        if index == -1 and appearing_times[w] == 0:
            print(-1)
            exit()
        elif index == -1:
            break
        else:
            dict[w].append(index)
            appearing_times[w] += 1

# how many times s is repeated
count = 0
# 0 <= length <= s_num - 1
s_index = 0
w_pre = 'none'

for w in t:
    idx = bisect.bisect_left(dict[w], s_index)
    if w == w_pre:
        idx += 1
        if idx == appearing_times[w]:
            count += 1
            idx = 0

    if idx < appearing_times[w]:
        s_index = dict[w][idx]
    else:
        count += 1
        s_index = dict[w][0]
    w_pre = w

print(count * s_num + s_index + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
length = 0

for _ in range(N):
    s = [v for v in input()]
    s.sort()

    hit = 0
    for i in range(length):
        t, num = S[i]
        if s == t:
            S[i] = (t, num + 1)
            hit = 1
            break
    if hit == 0:
        S.append((s, 1))
        length += 1

ans = 0
for i in range(length):
    t, num = S[i]
    ans += (num * (num - 1)) // 2
print(ans)

Fixed submission:
N = int(input())
dic = {}
ans = 0
for i in range(N):
    s = [v for v in input()]
    s.sort()
    word = ''.join(s)    

    if word in dic:
        dic[word] += 1
    else:
        dic[word] = 1

for word in dic:
    num = dic[word]
    ans += (num * (num - 1)) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
ans = 0
for i in range(N):
    s = [v for v in input()]
    s.sort()

    for t in S:
        if s == t:
            ans += 1

    S.append(s)

print(ans)

Fixed submission:
N = int(input())
dic = {}
ans = 0
for i in range(N):
    s = [v for v in input()]
    s.sort()
    word = ''.join(s)    

    if word in dic:
        dic[word] += 1
    else:
        dic[word] = 1

for word in dic:
    num = dic[word]
    ans += (num * (num - 1)) // 2

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

summation = [[] for i in range(10 ** 5 + 10 ** 4 + 1)]
for i in range(N):
    a, b = map(int, input().split())
    summation[a + b].append((a, b))

lst = []
for i in range(10 ** 5 + 10 ** 4):
    summation[i].sort()
    if summation[i] != []:
        for v in summation[i]:
            lst.append(v)

ans = 0
for i in range(M):
    remain = M - i
    if lst != []:
        while True:
            a, b = lst.pop()
            if a > remain:
                continue
            else:
                ans += b
                break
    else:
        break

print(ans)

Fixed submission:
import heapq

N, M = map(int, input().split())
dict = {}
keys = set([])
for i in range(N):
    a, b = map(int, input().split())
    if a in keys:
        dict[a].append(b)
    else:
        keys.add(a)
        dict[a] = [b]


cand = []
cand_num = 0
val = 0
for a in range(1, M + 1):
    # insert values in cand
    if a in keys:
        for b in dict[a]:
            heapq.heappush(cand, (-b, a))
            cand_num += 1

    if cand_num != 0:
        (b_0, a_0)= heapq.heappop(cand)
        cand_num -= 1
        val += -b_0
    else:
        pass

print(val)
Buggy python submission (verdict: Runtime Error):
a, b, cx = map(int, input().split())

d = a - b
print(max(0, c - d))

Fixed submission:

a, b, c = map(int, input().split())

d = a - b
print(max(0, c - d))
Buggy python submission (verdict: Time Limit Exceeded):
S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])


Fixed submission:
S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6) ################「再帰回数上限解放」######################

S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])


Fixed submission:
S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = []
for i in range(N):
        a = int(input())
        A.append(a)

for i in range(N):
        B = A[:i] + A[i+1:]
        print(max(B))

Fixed submission:
import numpy as np

N = int(input())
A = []
for i in range(N):
        a = int(input())
        A.append(a)
 
idx = np.argmax(np.array(A))
idx2 = np.argmax(np.array(A[:idx] + A[idx+1:]))
if idx2 >= idx:
        idx2 += 1

for i in range(N):
        if i != idx:
                print(A[idx])
        else:
                print(A[idx2])
Buggy python submission (verdict: Runtime Error):
import operator as op
from functools import reduce
 
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
 
 
N, K = list(map(int, input().split()))
 
def num(i):
    if i > N - K + 1:
        return 0
    else:
        num1 = int(ncr(N-K+1, i)) % (10**9 + 7)
        num2 = int(ncr(K-1, i-1)) % (10**9 + 7)
        num = (num1 * num2) % (10**9 + 7)
        return num
 
 
for i in range(1, K+1):
    print(num(i))

Fixed submission:
import operator as op
from functools import reduce
 
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom
 
 
N, K = list(map(int, input().split()))
 
def num(i):
    if i > N - K + 1:
        return 0
    else:
        num1 = ncr(N-K+1, i) % (10**9 + 7)
        num2 = ncr(K-1, i-1) % (10**9 + 7)
        num = (num1 * num2) % (10**9 + 7)
        return num
 
 
for i in range(1, K+1):
    print(num(i))

Buggy python submission (verdict: Runtime Error):
import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom


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

def num(i):
    if i > N - K + 1:
        return 0
    else:
        num1 = ncr(N-K+1, i) % (10**9 + 7)
        num2 = ncr(K-1, i-1) % (10**9 + 7)
        num = (num1 * num2) % (10**9 + 7)
        return int(num)


for i in range(1, K+1):
    print(num(i))

Fixed submission:
import operator as op
from functools import reduce
 
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom
 
 
N, K = list(map(int, input().split()))
 
def num(i):
    if i > N - K + 1:
        return 0
    else:
        num1 = ncr(N-K+1, i) % (10**9 + 7)
        num2 = ncr(K-1, i-1) % (10**9 + 7)
        num = (num1 * num2) % (10**9 + 7)
        return num
 
 
for i in range(1, K+1):
    print(num(i))
Buggy python submission (verdict: Runtime Error):
i = int(input())
S = []
while i > 0:
    S.append(i%10)
    i //= 10 # 必須
S.reverse()
if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print('Bad')
else:
    print('Good')

Fixed submission:
S = input()

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print('Bad')
else:
    print('Good')

Buggy python submission (verdict: Runtime Error):
S = int(input())
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
    print('Bad')
else:
    print('Good')

Fixed submission:
S = input()

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print('Bad')
else:
    print('Good')
Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // math.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)

Fixed submission:
import fractions

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // fractions.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)

Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // math.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)

Fixed submission:
import fractions

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // fractions.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))

# 最短距離が１の頂点の組は(N - 1)個
# 最短距離が２の頂点の組は(N - 1) * (N - 2) // 2個以下
# （star型のときが等号成立）

# よってK > (N - 1) * (N - 2) // 2なら解なし

if K > (N - 1) * (N - 2) // 2:
    print(-1)

# Kがこれ以下の場合はグラフが実際に構築可能である。
# ウニみたいな形を作ってとげ部分をいくつかつなげばよい。
# （単純グラフは二重辺や自己ループがなければ、通常のループはOK!!!）

else:
    dif = (N - 1) * (N - 2) // 2 - K
    print(N - 1 + dif)
    
    for i in range(N - 1):
        print(' '.join(map(str, [1, i + 2])))
    
    first = 2
    while dif >= N - first:
        for j in range(first + 1, N + 1):
            print(' '.join(map(str, [first, j])))
        dif -= N - first
        first += 1

    for k in range(dif):
        print(' '.join(map(str, [first, first + 1 + k])))


Fixed submission:
import itertools

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

# 最短距離が１の頂点の組は(N - 1)個以下
# 最短距離が２の頂点の組は(N - 1) * (N - 2) // 2個以下
# （star型のときが等号成立）

# よってK > (N - 1) * (N - 2) // 2なら解なし

if K > (N - 1) * (N - 2) // 2:
    print(-1)

# Kがこれ以下の場合はグラフが実際に構築可能である。
# ウニみたいな形を作ってとげ部分をいくつかつなげばよい。
# （単純グラフは二重辺や自己ループがなければ、通常のループはOK!!!）

else:
    diff = (N - 1) * (N - 2) // 2 - K
    print(N - 1 + diff)
    
    for i in range(N - 1):
        print(' '.join(map(str, [1, i + 2])))

    lst = list(range(2, N+1))
    combi = list(itertools.combinations(lst, 2))
    for i in range(diff):
        print(' '.join(map(str, combi[i])))

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))

# 最短距離が１の頂点の組は(N - 1)個
# 最短距離が２の頂点の組は(N - 1) * (N - 2) // 2個以下
# （star型のときが等号成立）

# よってK > (N - 1) * (N - 2) // 2なら解なし

if K > (N - 1) * (N - 2) // 2:
    print(-1)

# Kがこれ以下の場合はグラフが実際に構築可能である。
# ウニみたいな形を作ってとげ部分をいくつかつなげばよい。
# （単純グラフは二重辺や自己ループがなければ、通常のループはOK!!!）

else:
    dif = (N - 1) * (N - 2) // 2 - K
    print(N - 1 + dif)
    
    for i in range(N - 1):
        print(' '.join(map(str, [1, i + 2])))
    
    first = 2
    while dif >= N - first:
        for j in range(first + 1, N + 1):
            print(' '.join(map(str, [first, j])))
        dif -= N - first
        first += 1

    for k in range(dif):
        print(' '.join(map(str, [first, first + 1 + k])))


Fixed submission:
import itertools

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

# 最短距離が１の頂点の組は(N - 1)個以下
# 最短距離が２の頂点の組は(N - 1) * (N - 2) // 2個以下
# （star型のときが等号成立）

# よってK > (N - 1) * (N - 2) // 2なら解なし

if K > (N - 1) * (N - 2) // 2:
    print(-1)

# Kがこれ以下の場合はグラフが実際に構築可能である。
# ウニみたいな形を作ってとげ部分をいくつかつなげばよい。
# （単純グラフは二重辺や自己ループがなければ、通常のループはOK!!!）

else:
    diff = (N - 1) * (N - 2) // 2 - K
    print(N - 1 + diff)
    
    for i in range(N - 1):
        print(' '.join(map(str, [1, i + 2])))

    lst = list(range(2, N+1))
    combi = list(itertools.combinations(lst, 2))
    for i in range(diff):
        print(' '.join(map(str, combi[i])))
Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())

order = list(map(int, input().split()))
A = [order[1]]
len_A = 1
B = order[2]

for i in range(Q-1):
        order = list(map(int, input().split()))
        if order[0] == 1:
                B += order[2]
                idx = 0
                while idx < len_A and A[idx] < order[1]:
                        idx += 1
                A = A[:idx] + [order[1]] + A[idx:]
                len_A += 1
        else:
                if len_A % 2 == 1:
                        min_x = A[(len_A - 1) // 2]
                        min_f = B
                        for i in range(len_A):
                                min_f += abs(min_x - A[i])
                        print('{} {}'.format(min_x, min_f))
                else:
                        min_x = A[-1 + len_A // 2]
                        min_f = B
                        for i in range(len_A):
                                min_f += abs(min_x - A[i])
                        print('{} {}'.format(min_x, min_f))


Fixed submission:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

def main():
    Left = [10**10] # queri_num == 1の時はこっちが１多いことにする
    Right = [10**10]
    queri_num = 0 # mod 2
    const = 0
    min_val = 0

    """
    [a1, a2, ..., ai]の中央値を高速に求めないといけない所で分からず諦めた。。。

    発想は単純で、左側パートと右側パートを分けて管理しておいて、新しいクエリが来るごとに
    aを左に入れるか右に入れるか決めれば良い。
    ただし左右のパートをリストで管理するとaの挿入にO(N)かかってしまうので、ここでは
    ヒープによって管理する。なので挿入はO(logN)で可能。

    あと中央値における関数の最小値も求めないといけないが、これは基本的には単に|a - median|
    増えるだけなので、これもaの挿入時に逐次O(1)で決定可能。
    """

    Q = int(input())
    for _ in range(Q):
        queri = list(map(int, input().split()))
        if queri[0] == 2:
            x = -heappop(Left)
            print("{} {}".format(x, min_val + const))
            heappush(Left, -x)
        elif queri_num == 1:
            queri_num = 0
            const += queri[2]
            a = queri[1]
            mid = -heappop(Left)
            if a < mid:
                min_val += mid - a
                heappush(Left, -a)
                heappush(Right, mid)
            else:
                min_val += a - mid
                heappush(Left, -mid)
                heappush(Right, a)
        elif queri_num == 0:
            queri_num = 1
            const += queri[2]
            a = queri[1]
            left = -heappop(Left)
            right = heappop(Right)
            if a < left:
                min_val += left - a
                heappush(Left, -a)
                heappush(Left, -left)
                heappush(Right, right)
            elif a < right:
                # min_val is constant
                heappush(Left, -left)
                heappush(Left, -a)
                heappush(Right, right)
            else:
                min_val += a - right
                heappush(Left, -left)
                heappush(Left, -right)
                heappush(Right, a)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    
    """
    もし負の数が偶数個存在すればそれらはすべて正の数にできる。
    もし負の数が奇数個存在すればそれは最終的に１個にできる。
    """

    idx = bisect_left(A, 0)
    if idx % 2 == 0:
        print(sum(A[idx:]) - sum(A[:idx]))
    else:
        cand1 = sum(A[idx:]) - sum(A[:idx]) + A[idx - 1] * 2
        cand2 = sum(A[idx:]) - sum(A[:idx]) - A[idx] * 2
        print(max(cand1, cand2))
    


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    
    """
    もし負の数が偶数個存在すればそれらはすべて正の数にできる。
    もし負の数が奇数個存在すればそれは最終的に１個にできる。
    """

    idx = bisect_left(A, 0)
    if idx % 2 == 0:
        print(sum(A[idx:]) - sum(A[:idx]))
    elif idx < len(A) :
        cand1 = sum(A[idx:]) - sum(A[:idx]) + A[idx - 1] * 2
        cand2 = sum(A[idx:]) - sum(A[:idx]) - A[idx] * 2
        print(max(cand1, cand2))
    else:
        print(-sum(A) + A[-1] * 2)
    


if __name__ == "__main__":
    main()