Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [1 for _ in range(n)]
def dfs1(x, p):
	for c in adj[x]:
		if c == p:
			continue
		dfs1(c, x)
		dp[x] *= dp[c]+1
		dp[x] %= m
	return

dfs1(0, -1)
ans = [0 for _ in range(n)]
ans[0] = dp[0]
def dfs2(x, p):
	l = len(adj[x])
	cuml = [1 for _ in range(l+2)]
	cumr = [1 for _ in range(l+2)]
	for i in range(l):
		cuml[i+1] = (cuml[i] * (dp[adj[x][i]] + 1)) % m
	for i in range(l-1, -1, -1):
		cumr[i+1] = (cumr[i+2] * (dp[adj[x][i]] + 1)) % m
	pres_x = dp[x]
	for i, c in enumerate(adj[x]):
		if c == p:
			continue
		pres_c = dp[c]
		dp[x] = (cuml[i] * cumr[i+2]) % m
		dp[c] *= dp[x] + 1
		dp[c] %= m
		ans[c] = dp[c]
		dfs2(c, x)
		dp[x] = pres_x
		dp[c] = pres_c
	return

dfs2(0, -1)
print(*ans, sep="\n")

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [1 for _ in range(n)]
def dfs1(x, p):
	for c in adj[x]:
		if c == p:
			continue
		dfs1(c, x)
		dp[x] *= dp[c]+1
		dp[x] %= m
	return

dfs1(0, -1)
ans = [0 for _ in range(n)]
ans[0] = dp[0]
def dfs2(x, p):
	l = len(adj[x])
	cuml = [1 for _ in range(l+2)]
	cumr = [1 for _ in range(l+2)]
	for i in range(l):
		cuml[i+1] = (cuml[i] * (dp[adj[x][i]] + 1)) % m
	for i in range(l-1, -1, -1):
		cumr[i+1] = (cumr[i+2] * (dp[adj[x][i]] + 1)) % m
	pres_x = dp[x]
	for i, c in enumerate(adj[x]):
		if c == p:
			continue
		pres_c = dp[c]
		dp[x] = (cuml[i] * cumr[i+2]) % m
		dp[c] *= dp[x] + 1
		dp[c] %= m
		ans[c] = dp[c]
		dfs2(c, x)
		dp[x] = pres_x
		dp[c] = pres_c
	return

dfs2(0, -1)
print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**10
n = int(input())
a = list(map(int, input().split()))

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	k = -30
	while a[i-1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j+k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	k = -30
	while a[i+1] * pow(4, k) < a[i]:
		k += 1
	for j in range(20):
		if j+k < 20:
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j+k, 0)]

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)

Fixed submission:
INF = 10**10
n = int(input())
a = list(map(int, input().split()))

dp_fr = [[INF for _ in range(20)] for _ in range(n)]
dp_ba = [[INF for _ in range(20)] for _ in range(n)]

#dp[i][j]: iまで考えてa_iを4^j倍したときの必要最小コスト
for j in range(20):
	dp_fr[0][j] = 2*j

for i in range(1, n):
	if a[i-1] < a[i]:
		k = 0
		while a[i-1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_fr[i][j] = 2*j + dp_fr[i-1][j+k]
			else:
				dp_fr[i][j] = 2*j + dp_fr[i-1][19] + 2*(i) * (j+k-19)
	else:
		k = 0
		while a[i-1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_fr[i][j] = 2*j + dp_fr[i-1][max(j-k, 0)]

for j in range(20):
	dp_ba[n-1][j] = 2*j

for i in range(n-2, -1, -1):
	if a[i+1] < a[i]:
		k = 0
		while a[i+1] * pow(4, k) < a[i]:
			k += 1
		for j in range(20):
			if j+k < 20:
				dp_ba[i][j] = 2*j + dp_ba[i+1][j+k]
			else:
				dp_ba[i][j] = 2*j + dp_ba[i+1][19] + 2*(n-i-1) * (j+k-19)
	else:
		k = 0
		while a[i+1] >= a[i] * pow(4, k+1):
			k += 1
		for j in range(20):
			dp_ba[i][j] = 2*j + dp_ba[i+1][max(j-k, 0)]

#print(*dp_fr, sep="\n")
#print(*dp_ba, sep="\n")

ans = min(dp_ba[0][0], n + dp_fr[n-1][0])
for i in range(n-1):
	ans = min(ans, dp_ba[i+1][0] + i+1 + dp_fr[i][0])

print(ans)
Buggy python submission (verdict: Runtime Error):
d = int(input())
if d == 25:
	print("Christmas")
elif d == 24:
	print("Christmas Eve")
elif d == 23:
	print("Christmas Eve Eve"):
else:
	print("Christmas Eve Eve Eve")

Fixed submission:
d = int(input())
if d == 25:
	print("Christmas")
elif d == 24:
	print("Christmas Eve")
elif d == 23:
	print("Christmas Eve Eve")
else:
	print("Christmas Eve Eve Eve")
Buggy python submission (verdict: Runtime Error):
from math import gcd

n, m = map(int, input().split())
s = input()
t = input()

if n % m != 0 and m % n != 0:
	print(n // gcd(n, m) * m)
elif n >= m:
	ok = True
	for i in range(m):
		if s[(n // m) * i] != t[i]:
			ok = False
			break
	if ok:
		print(n)
	else:
		print(-1)
else:
	ok = True
	for i in range(n):
		if t[(m // n) * i] != s[i]:
			ok = False
			break
	if ok:
		print(m)
	else:
		print(-1)


Fixed submission:
from fractions import gcd

n, m = map(int, input().split())
s = input()
t = input()

g = gcd(n, m)
lcm = n // g * m
ok = True
for i in range(n):
	if (i * (lcm // n)) % (lcm // m) == 0:
		if s[i] != t[(i * (lcm // n)) // (lcm // m)]:
			ok = False
			break
if ok:
	print(lcm)
else:
	print(-1)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

n = int(input())
v = list(map(int, input().split()))

one = sorted(Counter([v[i] for i in range(0, n, 2)]).items(), key=lambda x: x[1], reverse=True)
two = sorted(Counter([v[i] for i in range(1, n, 2)]).items(), key=lambda x: x[1], reverse=True)

print(one, two)
if one[0][0] != two[0][0]:
	print(n - one[0][1] - two[0][1])
else:
	if len(one) == 1 and len(two) == 1:
		print(n // 2)
	elif len(one) == 1:
		print(n // 2 - two[1][1])
	elif len(two) == 1:
		print(n // 2 - one[1][1])
	else:
		print(min(n - one[0][1] - two[1][1]), n - one[1][1] - two[0][1])

Fixed submission:
from collections import Counter

n = int(input())
v = list(map(int, input().split()))

one = sorted(Counter([v[i] for i in range(0, n, 2)]).items(), key=lambda x: x[1], reverse=True)
two = sorted(Counter([v[i] for i in range(1, n, 2)]).items(), key=lambda x: x[1], reverse=True)

#print(one, two)
if one[0][0] != two[0][0]:
	print(n - one[0][1] - two[0][1])
else:
	if len(one) == 1 and len(two) == 1:
		print(n // 2)
	elif len(one) == 1:
		print(n // 2 - two[1][1])
	elif len(two) == 1:
		print(n // 2 - one[1][1])
	else:
		print(min(n - one[0][1] - two[1][1], n - one[1][1] - two[0][1]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n = int(input())
ds = [list(map(int, input().split())) for _ in range(n)]
mod = (ds[0][0] + ds[0][1]) % 2
for i in range(2, n):
	if (ds[i][0] + ds[i][1]) % 2 != mod:
		print(-1)
		sys.exit()

m = max([abs(ds[i][0]) + abs(ds[i][1]) for i in range(n)])
if m == 0:
	print(2)
	print(1, 1)
	for _ in range(n):
		print("LR")
else:
	print(m)
	print(*[1 for _ in range(m)])
	for d in ds:
		ans = []
		if d[0] >= 0:
			ans += ["R"] * d[0]
		else:
			ans += ["L"] * abs(d[0])
		if d[1] >= 0:
			ans += ["U"] * d[1]
		else:
			ans += ["D"] * abs(d[1])
		ans += ["LR"] * ((m - abs(d[0]) - abs(d[1])) // 2)
		print(*ans, sep="")

Fixed submission:
import sys

n = int(input())
ds = [list(map(int, input().split())) for _ in range(n)]
mod = (ds[0][0] + ds[0][1]) % 2
for i in range(2, n):
	if (ds[i][0] + ds[i][1]) % 2 != mod:
		print(-1)
		sys.exit()

if mod == 1:
	m = 31
	arms = [1<<i for i in range(31, 0, -1)]
else:
	m = 32
	arms = [1<<i for i in range(31, 0, -1)] + [2]

print(m)
print(*[a//2 for a in arms])

for q in range(n):
	x, y = ds[q][0], ds[q][1]
	ans = ""
	u, v = x+y + (1<<31) - 1, x-y + (1<<31) - 1
	if mod == 0:
		u, v = u-1, v-1
	u_li = []
	v_li = []
	for i in range(31, 0, -1):
		if u >= (1<<i):
			u_li.append(1)
			u -= (1<<i)
		else:
			u_li.append(0)
		if v >= (1<<i):
			v_li.append(1)
			v -= (1<<i)
		else:
			v_li.append(0)

	for i in range(31):
		if u_li[i] and v_li[i]:
			ans += "R"
		elif u_li[i]:
			ans += "U"
		elif v_li[i]:
			ans += "D"
		else:
			ans += "L"

	if mod == 0:
		ans += "R"

	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, X = map(int, input().split())
x = list(map(int, input().split()))
x_sum = [0] # 1-indexed
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])

ans = float("inf")
for i in range(1, n):
	res = X * (i + n)
	res += 5 * (x_sum[-1] - x_sum[-i - 1])
	cost = 5
	j = 1
	while (j * i) + i + 1 <= n:
		#print(-(j * i) - 1, -(j * i) - i - 1)
		res += cost * (x_sum[-(j * i) - 1] - x_sum[-(j * i) - i - 1])
		cost += 2
		j += 1
	res += cost * (x_sum[-(j * i) - 1])

	ans = min(res, ans)

print(ans)

Fixed submission:
n, X = map(int, input().split())
x = list(map(int, input().split()))
x_sum = [0] # 1-indexed
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])

ans = float("inf")
for i in range(1, n):
	res = X * (i + n)
	res += 5 * (x_sum[-1] - x_sum[-i - 1])
	cost = 5
	j = 1
	while (j * i) + i + 1 <= n:
		#print(-(j * i) - 1, -(j * i) - i - 1)
		res += cost * (x_sum[-(j * i) - 1] - x_sum[-(j * i) - i - 1])
		cost += 2
		j += 1
	res += cost * (x_sum[-(j * i) - 1])

	ans = min(res, ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
if a != 2 and c != 2:
	print("Yes")
else:
	print("No")

Fixed submission:
a, b = map(int, input().split())
if a != 2 and b != 2:
	print("Yes")
else:
	print("No")
Buggy python submission (verdict: Runtime Error):
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for h in range(H)]
    cnt = 0
    out = []
    for h in range(H):
        for w in range(W):
            if A[h, w]%2 == 1:
                cnt += 1
                if w < W-1:
                    A[h, w+1] += 1
                    out.append(list(map(str, [h+1, w+1, h+1, w+2])))
                elif h < H-1:
                    A[h+1, w] += 1
                    out.append(list(map(str, [h+1, w+1, h+2, w+1])))
                else:
                    cnt -= 1
    print(cnt)
    for posi in out:
        print(" ".join(posi))


if __name__ == '__main__':
    main()


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

for h in range(H-1):
	for w in range(W-1):
		if a[h][w] % 2 == 1:
			ans.append([h+1, w+1, h+1, w+2])
			a[h][w+1] += 1
	if a[h][-1] % 2 == 1:
		ans.append([h+1, W, h+2, W])
		a[h+1][-1] += 1

for w in range(W-1):
	if a[H-1][w] % 2 == 1:
		ans.append([H, w+1, H, w+2])
		a[H-1][w+1] += 1

print(len(ans))
for an in ans:
	print(*an)

Buggy python submission (verdict: Runtime Error):
def main():
    H, W = map(int, input().split())
    A = [input().split() for h in range(H)]
    cnt = 0
    out = []
    for h in range(H):
        for w in range(W):
            if A[h][w]%2 == 1:
                cnt += 1
                if w < W-1:
                    A[h][w+1] += 1
                    out.append(list(map(str, [h+1, w+1, h+1, w+2])))
                elif h < H-1:
                    A[h+1][w] += 1
                    out.append(list(map(str, [h+1, w+1, h+2, w+1])))
                else:
                    cnt -= 1
    print(cnt)
    for posi in out:
        print(" ".join(posi))


if __name__ == '__main__':
    main()


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

for h in range(H-1):
	for w in range(W-1):
		if a[h][w] % 2 == 1:
			ans.append([h+1, w+1, h+1, w+2])
			a[h][w+1] += 1
	if a[h][-1] % 2 == 1:
		ans.append([h+1, W, h+2, W])
		a[h+1][-1] += 1

for w in range(W-1):
	if a[H-1][w] % 2 == 1:
		ans.append([H, w+1, H, w+2])
		a[H-1][w+1] += 1

print(len(ans))
for an in ans:
	print(*an)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
k, n = map(int, input().split())

list_size = 5000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = []
for i in range(2, k+2):
	num = 0
	if i%2 == 1:
		for j in range(0, i//2+1):
			#num += comb(i//2, j) * comb(n-1, j-1) * pow(2, j, MOD) * comb(n+k-i-j, k-i)
			num += comb(i//2, j) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			num %= MOD
	else:
		for j in range(0, i//2):
			#num += comb(i//2-1, j) * comb(n-1, j-1) * pow(2, j, MOD) * comb(n+k-i-j, k-i)
			num += comb(i//2-1, j) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			#num += comb(i//2-1, j) * comb(n-2, j-1) * pow(2, j, MOD) * comb(n+k-i-j-1, k-i)
			num += comb(i//2-1, j) * pow(2, j, MOD) * comb(n+k-i-1, k-i+j)
			num %= MOD
	ans.append(num)

print(*ans, sep="\n")
ans = reversed(ans[:k-1])
print(*ans, sep="\n")

Fixed submission:
MOD = 998244353
k, n = map(int, input().split())

list_size = 5000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = []
for i in range(2, k+2):
	num = 0
	if i%2 == 1:
		for j in range(0, i//2+1):
			#num += comb(i//2, j) * comb(n-1, j-1) * pow(2, j, MOD) * comb(n+k-i-j, k-i)
			num += comb(i//2, j) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			num %= MOD
	else:
		for j in range(0, i//2):
			#num += comb(i//2-1, j) * comb(n-1, j-1) * pow(2, j, MOD) * comb(n+k-i-j, k-i)
			num += comb(i//2-1, j) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			#num += comb(i//2-1, j) * comb(n-2, j-1) * pow(2, j, MOD) * comb(n+k-i-j-1, k-i)
			num += comb(i//2-1, j) * pow(2, j, MOD) * comb(n+k-i-1, k-i+j)
			num %= MOD
	ans.append(num)

print(*ans, sep="\n")
ans = reversed(ans[:k-1])
print(*ans, sep="\n")
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

n, k = map(int, input().split())
x = list(map(int, input().split()))
pos = bisect_left(x, 0)
#print(bisect_left(x, 0))


if n == 1:
	print(abs(x[0]))
elif x[0] >= 0:
	print(x[k - 1])
elif x[-1] <= 0:
	print(-x[-k - 1])
else:
	ans = float("inf")
	if pos + k <= n:
		ans = x[pos + k - 1]
	if x[pos] == 0:
		if pos - k + 1 >= 0:
			ans = min(ans, -x[pos - k + 1])
	else:
		if pos - k >= 0:
			ans = min(ans, -x[pos - k])
	for i in range(max(0, k - pos - 1), min(k - 1, n - pos)):
		#print(i)
		right = x[pos + i]
		left = -x[pos - (k - i - 1)]
		#print(right, left)
		ans = min(ans, 2 * right + left, 2 * left + right)

	print(ans)


Fixed submission:
from bisect import bisect_left

n, k = map(int, input().split())
x = list(map(int, input().split()))
pos = bisect_left(x, 0)
#print(bisect_left(x, 0))


if n == 1:
	print(abs(x[0]))
elif x[0] >= 0:
	print(x[k - 1])
elif x[-1] <= 0:
	print(-x[-k])
else:
	ans = float("inf")
	if pos + k <= n:
		ans = x[pos + k - 1]
	if x[pos] == 0:
		if pos - k + 1 >= 0:
			ans = min(ans, -x[pos - k + 1])
	else:
		if pos - k >= 0:
			ans = min(ans, -x[pos - k])
	for i in range(max(0, k - pos - 1), min(k - 1, n - pos)):
		#print(i)
		right = x[pos + i]
		left = -x[pos - (k - i - 1)]
		#print(right, left)
		ans = min(ans, 2 * right + left, 2 * left + right)

	print(ans)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

n, k = map(int, input().split())
x = list(map(int, input().split()))
pos = bisect_left(x, 0)
#print(bisect_left(x, 0))

if x[0] >= 0:
	print(x[k - 1])
elif x[-1] <= 0:
	print(-x[-k - 1])
else:
	ans = float("inf")
	if pos + k <= n:
		ans = x[pos + k - 1]
	if x[pos] == 0:
		if pos - k + 1 >= 0:
			ans = min(ans, -x[pos - k + 1])
	else:
		if pos - k >= 0:
			ans = min(ans, -x[pos - k])
	for i in range(max(0, k - pos - 1), min(k - 1, n - pos)):
		#print(i)
		right = x[pos + i]
		left = -x[pos - (k - i - 1)]
		#print(right, left)
		ans = min(ans, 2 * right + left, 2 * left + right)

	print(ans)


Fixed submission:
from bisect import bisect_left

n, k = map(int, input().split())
x = list(map(int, input().split()))
pos = bisect_left(x, 0)
#print(bisect_left(x, 0))


if n == 1:
	print(abs(x[0]))
elif x[0] >= 0:
	print(x[k - 1])
elif x[-1] <= 0:
	print(-x[-k])
else:
	ans = float("inf")
	if pos + k <= n:
		ans = x[pos + k - 1]
	if x[pos] == 0:
		if pos - k + 1 >= 0:
			ans = min(ans, -x[pos - k + 1])
	else:
		if pos - k >= 0:
			ans = min(ans, -x[pos - k])
	for i in range(max(0, k - pos - 1), min(k - 1, n - pos)):
		#print(i)
		right = x[pos + i]
		left = -x[pos - (k - i - 1)]
		#print(right, left)
		ans = min(ans, 2 * right + left, 2 * left + right)

	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	# あとで全体を-min_tmp+1だけ足さないとバグる
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	# あとで全体を-min_tmp+1だけ足さないとバグる
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

n, k = map(int, input().split())
x = list(map(int, input().split()))
pos = bisect_left(x, 0)
#print(bisect_left(x, 0))

if x[0] >= 0:
	print(x[k - 1])
elif x[-1] <= 0:
	print(-x[-k])
else:
	ans = float("inf")
	if pos + k <= n:
		ans = x[pos + k - 1]
	if x[pos] == 0:
		if pos - k - 1 >= 0:
			ans = min(ans, -x[pos - k - 1])
	else:
		if pos - k >= 0:
			ans = min(ans, -x[pos - k])
	for i in range(max(pos, k - 1 - pos), min(pos + k - 1, n)):
		#print(i)
		right = x[i]
		left = -x[pos - (k - (i - pos + 1))]
		#print(right, left)
		ans = min(ans, 2 * right + left, 2 * left + right)

	print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def b_sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def b_add(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

fr, ba = min(a), max(a)+1

while ba - fr > 1:
	mi = (fr+ba) // 2
	bit = BIT(n+1)
	res = 0
	inv = [0]
	min_tmp = 0
	# あとで全体を-min_tmp+1だけ足さないとバグる
	for j in range(n):
		if a[j] >= mi:
			inv.append(inv[-1]+1)
		else:
			inv.append(inv[-1]-1)
			min_tmp = min(min_tmp, inv[-1])

	for j in range(n+1):
		res += bit.b_sum(inv[j] - min_tmp + 1)
		bit.b_add(inv[j] - min_tmp + 1, 1)

	if res >= (n * (n+1) / 4):
		fr = mi
	else:
		ba = mi

print(fr)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

d, g = map(int, input().split())
g = g // 100
p = []
c = []

for _ in range(d):
	pp, cc = map(int, input().split())
	p.append(pp)
	c.append(cc // 100)

ans = float("inf")
for array in permutations(range(d)):
	gap = g
	num = 0
	for a in array:
		if p[a] * (a + 1) >= gap:
			num += (gap - 1) // (a + 1) + 1
			break
		elif p[a] * (a + 1) + c[a] >= gap:
			num += p[a]
			break
		else:
			num += p[a]
			gap -= p[a] * (a + 1) + c[a]

	if num < ans:
		ans = num

print(ans)

Fixed submission:
from itertools import permutations

d, g = map(int, input().split())
g = g // 100
p = []
c = []

for _ in range(d):
	pp, cc = map(int, input().split())
	p.append(pp)
	c.append(cc // 100)

ans = float("inf")
for array in permutations(range(d)):
	gap = g
	num = 0
	for a in array:
		if p[a] * (a + 1) >= gap:
			num += (gap - 1) // (a + 1) + 1
			break
		elif p[a] * (a + 1) + c[a] >= gap:
			num += p[a]
			break
		else:
			num += p[a]
			gap -= p[a] * (a + 1) + c[a]

	if num < ans:
		ans = num

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

dp1 = [x for x in a]
dp2 = [0 for _ in range(1<<n)]

for j in range(n+1):
	for i in range(1<<n):
		if i & (1<<j):
			if dp1[i & ~(1<<j)] >= dp1[i]:
				if dp2[i & ~(1<<j)] >= dp1[i]:
					dp2[i] = dp2[i & ~(1<<j)]
				else:
					dp2[i] = dp1[i]
				dp1[i] = dp1[i & ~(1<<j)]
			else:
				if dp1[i & ~(1<<j)] >= dp2[i]:
					dp2[i] = dp1[i & ~(1<<j)]

ans = 0
for i in range(1, 1<<n):
	ans = max(ans, dp1[i]+dp2[i])
	print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp1 = [x for x in a]
dp2 = [0 for _ in range(1<<n)]

for j in range(n+1):
	for i in range(1<<n):
		if i & (1<<j):
			if dp1[i & ~(1<<j)] >= dp1[i]:
				if dp2[i & ~(1<<j)] >= dp1[i]:
					dp2[i] = dp2[i & ~(1<<j)]
				else:
					dp2[i] = dp1[i]
				dp1[i] = dp1[i & ~(1<<j)]
			else:
				if dp1[i & ~(1<<j)] >= dp2[i]:
					dp2[i] = dp1[i & ~(1<<j)]

ans = 0
for i in range(1, 1<<n):
	ans = max(ans, dp1[i]+dp2[i])
	print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations, product
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

iwakan_min = 500001

def modthree(i, j):
	if (i + j) % 3 == 0:
		return p
	elif (i + j) % 3 == 1:
		return q
	else:
		return r

for p, q, r in permutations(range(0, C), r=3):
	iwakan = 0
	for i, j in product(range(N), repeat=2):
		iwakan += D[c[i][j] - 1][modthree(i, j)]
	if iwakan < iwakan_min:
		iwakan_min = iwakan

print(iwakan_min)

Fixed submission:
from itertools import permutations, product
from collections import Counter
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

zero = []
one = []
two = []
for i, j in product(range(N), repeat=2):
	if (i + j) % 3 == 0:
		zero.append(c[i][j])
	elif (i + j) % 3 == 1:
		one.append(c[i][j])
	else:
		two.append(c[i][j])

zero = Counter(zero)
one = Counter(one)
two = Counter(two)

iwakan_min = float("inf")

for p, q, r in permutations(range(0, C), r=3):
	iwakan = 0
	for key, value in zero.items():
		iwakan += value * (D[key - 1][p])
	for key, value in one.items():
		iwakan += value * (D[key - 1][q])
	for key, value in two.items():
		iwakan += value * (D[key - 1][r])
	if iwakan < iwakan_min:
		iwakan_min = iwakan

print(iwakan_min)