Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02669 (python)

Fixed submission:
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])

Buggy submission (verdict: Runtime Error):
import sys
from numba import njit
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False
	@njit
	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])
Problem p02698 (python)

Fixed submission:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

INF = 10**10
dp = [INF for _ in range(n)]
ans = [0 for _ in range(n)]

def dfs(x, p):
	ans[x] = bisect_left(dp, INF)
	for v in adj[x]:
		if v == p:
			continue
		ind = bisect_left(dp, a[v])
		pres = dp[ind]
		dp[ind] = a[v]
		dfs(v, x)
		dp[ind] = pres
	return

dp[0] = a[0]
dfs(0, -1)
print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

INF = 10**6
dp = [INF for _ in range(n)]
ans = [0 for _ in range(n)]

def dfs(x, p):
	ans[x] = bisect_left(dp, INF)
	for v in adj[x]:
		if v == p:
			continue
		ind = bisect_left(dp, a[v])
		pres = dp[ind]
		dp[ind] = a[v]
		dfs(v, x)
		dp[ind] = pres
	return

dp[0] = a[0]
dfs(0, -1)
print(*ans, sep="\n")
Problem p02734 (python)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(3001)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(s+1)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)
Problem p02756 (python)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]

s = input()
#n = len(s)
q = int(input())
front = ""
back = ""
sgn = 0
for _ in range(q):
	query = input().split()
	if query[0] == "1":
		sgn ^= 1
	else:
		f, c = int(query[1])-1, query[2]
		if f ^ sgn == 0:
			front += c
		else:
			back += c
if not sgn:
	print(front[::-1] + s + back)
else:
	print(back[::-1] + s[::-1] + front)

Buggy submission (verdict: Runtime Error):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

s = input()
n = len(s)
q = int(input())
front = ""
back = ""
sgn = 0
for _ in range(q):
	query = input().split()
	if query[0] == "1":
		sgn ^= 1
	else:
		f, c = int(query[1])-1, query[2]
		if f ^ sgn == 0:
			front += c
		else:
			back += c
if not sgn:
	print(front[::-1] + s + back)
else:
	print(back[::-1] + s[::-1] + front)
Problem p02809 (python)

Fixed submission:
import sys
from itertools import permutations
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n-3:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1 and not used[k]:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

yet = [i for i in range(1, n+1) if not used[i]]
for p in permutations(yet):
	if p[0] != ng and p[1] != a[p[0]] and p[2] != a[p[1]]:
		ans += list(p)
		break

print(*ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1 and not used[k]:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

print(*ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = [0] + list(map(int, input().split()))
if n == 2:
	print(-1)
	sys.exit()
used = [False for _ in range(n+1)]
hate = dict()
for x in a[1:]:
	if x in hate:
		hate[x] += 1
	else:
		hate[x] = 1
cur = 1
ng = 0
ans = []
while len(ans) < n:
	if len(hate) == 2:
		worst = False
		for k, v in hate.items():
			if v == n - len(ans) - 1:
				worst = k
				break
		if worst:
			ans.append(k)
			used[k] = True
			ng = a[k]
			hate[a[k]] -= 1
			if hate[a[k]] == 0:
				del hate[a[k]]
			continue

	while used[cur]:
		cur += 1

	if cur == ng:
		cur_copy = cur+1
		while used[cur_copy]:
			cur_copy += 1
		ans.append(cur_copy)
		used[cur_copy] = True
		ng = a[cur_copy]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]
	else:
		ans.append(cur)
		used[cur] = True
		ng = a[cur]
		hate[ng] -= 1
		if hate[ng] == 0:
			del hate[ng]

print(*ans)
Problem p02814 (python)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])
		if lcm > m:
			print(0)
			sys.exit()

	divs = 0
	for x in a:
		divs += (lcm//x)%2
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)

Buggy submission (verdict: Runtime Error):
import sys
def input():
	return sys.stdin.readline()[:-1]

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])
		if lcm > x:
			print(0)
			sys.exit()

	divs = 0
	for x in a:
		divs += (lcm//x)%2
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)

Buggy submission (verdict: Runtime Error):
from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

lcm = a[0]*a[1]//gcd(a[0], a[1])
for i in range(2, n):
	lcm = lcm * a[i] // gcd(lcm, a[i])

divs = sum([(lcm//x)%2 for x in a])
if divs < n:
	print(0)
else:
	print((m//lcm+1)//2)
Problem p02840 (python)

Fixed submission:
import sys
from fractions import gcd
n, x, d = map(int, input().split())
"""
数列からi個選ぶことを考えると
i*xに加えて足されるdの数はi(i-1)/2 〜 i(2n-1-i)/2 の任意の個数
i > j なるjで代替されるような和はこのうちどのような条件を満たすものか？
g = gcd(x, d). l = lcm(x, d)として
(g*l = x*d)
i*x + k*d が条件を満たすとすると
i*x + k*d = (i - d/g)x + (k + x/g)d が成り立つ
(i - d/g)(2n - 1 - i + d/g)/2 >= (k + x/g) となるような最大のkを求めれば，
k以下はすべてかぶる，k+1以上はすべてかぶらない

x<0 のときは
(i - d//g) * (i - d//g - 1)//2 <= (k + x//g) <= (i - d//g) * (2*n - 1 - i + d//g)//2
(i - d//g) * (i - d//g - 1)//2 - x//g <= k <= (i - d//g) * (2*n - 1 - i + d//g)//2 - x//g
となるようなkにおいてはかぶる
"""
if x == 0 and d == 0:
	print(1)
	sys.exit()
elif d == 0:
	print(n+1)
	sys.exit()

if x < 0 and x + (n-1) * d < 0:
	x, d = -x, -d

if x >= 0 and d < 0:
	x, d = x + (n-1) * d, -d

#print(x, d)
g = gcd(x, d)

ans = 1
if x >= 0:
	for i in range(1, n+1):
		#print((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g)
		k = max((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (i-1) // 2 - 1)
		#print(k)
		ans += max((i * (2*n-1-i)) // 2 - k, 0)

else:
	for i in range(1, n+1):
		overlap_u = min((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (2*n-1-i) // 2)
		overlap_l = max((i - d//g) * (i - d//g - 1) // 2 - x//g, i * (i-1) // 2)
		ans += i * (2*n-1-i) // 2 - i * (i-1) // 2 + 1 - max(overlap_u - overlap_l + 1, 0)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
from math import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d

ans = n
g = gcd(x, d)

for i in range(2, n+1):
	k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, -1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)
Problem p02867 (python)

Fixed submission:
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])
a = [(x[0], i) for i, x in enumerate(c)]
b = [x[1] for x in c]
a.sort()
for i in range(n):
	if a[i][0] > b[i]:
		print("No")
		sys.exit()
cur, cnt = 0, 0
while a[cur][1] != 0:
	cnt += 1
	cur = a[cur][1]
if cnt < n-1:
	print("Yes")
else:
	for i in range(n-1):
		if a[i+1][0] <= b[i]:
			print("Yes")
			break
	else:
		print("No")

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])
a = [(x[0], i) for i, x in enumerate(c)]
b = [x[1] for x in c]
a.sort()
for i in range(n):
	if a[i][0] > b[i]:
		print("No")
		sys.exit()
cur, cnt = 0, 0
while a[cur][1] != 0:
	cnt += 1
	cur = a[cur][1]
if cnt < n-1:
	print("Yes")
else:
	for i in range(n-1):
		if a[i] <= b[i+1]:
			print("Yes")
			break
	else:
		print("No")
Problem p02929 (python)

Fixed submission:
import sys
n = int(input())
s = input()
if s[0] == "W":
  print(0)
  sys.exit()
MOD = 10**9+7
ans = 1
cnt = 1
right = 1
for i in range(2*n-1):
  if s[i+1] == s[i]:
    right ^= 1
  if right:
    cnt += 1
  else:
    ans *= cnt
    ans %= MOD
    cnt -= 1
if cnt != 0:
  print(0)
else:
  for i in range(1, n+1):
    ans *= i
    ans %= MOD
  print(ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
s = input()
if s[0] == "W":
  print(0)
  sys.exit()
MOD = 10**9+7
ans = 1
cnt = 1
for i in range(2*n):
  if s[i+1] != s[i]:
    cnt += 1
  else:
    ans *= cnt
    ans %= MOD
    cnt -= 1
if cnt != 0:
  print(0)
else:
  print(ans)
Problem p02940 (python)

Fixed submission:
n = int(input())
s = input()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
pre = ["", ["", ""]]
for i in range(3*n):
  if t != 0 and s[i] not in pre[1]:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      pre[1] = ["", ""]
  elif s[i] == pre[0] or o == 0:
    o += 1
    ans *= z
    ans %= mod
    z -= 1
    pre[0] = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    pre[1] = [pre[0], s[i]]
    if o == 0:
      pre[0] = ""

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
s = ineput()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
pre = ["", ["", ""]]
for i in range(3*n):
  if t != 0 and s[i] not in pre[1]:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      pre[1] = ["", ""]
  elif s[i] == pre[0] or o == 0:
    o += 1
    ans *= z
    ans %= mod
    z -= 1
    pre[0] = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    pre[1] = [pre[0], s[i]]
    if o == 0:
      pre[0] = ""

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
O, T = "", ""
for i in range(3*n):
  if T != "" and s[i] != O and s[i] != T:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      T = ""
  elif s[i] == O or O == "":
    o += 1
    ans *= zg
    ans %= mod
    z -= 1
    O = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    T = s[i]
    if o == 0:
      O = ""

print(ans)
Problem p02950 (python)

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

list_size = p-1

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)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

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

def comb(n, r):
	if n < r:
		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]) % p) * f_r_list[r - 1]) % p 

pows = [[1] for x in range(p)]
for i in range(p):
	for _ in range(p-1):
		pows[i].append((pows[i][-1] * i) % p)

ans = [0 for _ in range(p)]
for i, x in enumerate(a):
	if x == 0:
		continue
	ans[0] += 1
	ans[0] %= p
	for j in range(p):
		ans[j] -= pows[(p-i)%p][p-1-j] * comb(p-1, j)
		ans[j] %= p

print(*ans)

Buggy submission (verdict: Runtime Error):
p = int(input())
a = list(map(int, input().split()))

list_size = p-1

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)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

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

def comb(n, r):
	if n < r:
		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]) % p) * f_r_list[r - 1]) % p 

pows = [[1] for x in range(p)]
for i in range(p):
	for _ in range(p-1):
		pows[i].append((pows[i][-1] * i) % p)

ans = [0 for _ in range(p)]
for i, x in enumerate(a):
	if x == 0:
		continue
	ans[0] += 1
	ans[0] %= p
	for j in range(p):
		ans[j] -= pows[p-i][p-1-j] * comb(p-1, j)
		ans[j] %= p

print(*ans)
Problem p02975 (python)

Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l = len(set(a))
if l > 3:
	print("No")
elif l == 1:
	if a[0] == 0:
		print("Yes")
	else:
		print("No")
elif n%3 != 0:
	print("No")
elif l == 2:
	if 0 not in set(a):
		print("No")
	elif a.count(0) == n//3:
		print("Yes")
	else:
		print("No")
else:
	for x in list(set(a)):
		if a.count(x) != n//3:
			print("No")
			break
	else:
		if list(set(a))[0] ^ list(set(a))[1] == list(set(a))[2]:
			print("Yes")
		else:
			print("No")

Buggy submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l = len(set(a))
if l > 3:
	print("No")
elif l == 1:
	if a[0] == 0:
		print("Yes")
	else:
		print("No")
elif n%3 != 0:
	print("No")
elif l == 2:
	if 0 not in set(a):
		print("No")
	elif a.count(0) == n//3:
		print("Yes")
	else:
		print("No")
else:
	for x in list(set(a)):
		if a.count(x) != n//3:
			print("No")
			break
	elif list(set(a))[0] ^ list(set(a))[1] == list(set(a))[2]:
		print("Yes")
	else:
		print("No")
Problem p03026 (python)

Fixed submission:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
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)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0)
print(sum(c) - max(c))
print(*num)

Buggy submission (verdict: Runtime Error):
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
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)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop
n = int(input())
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)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x, par):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v, x)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop
n = int(input())
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)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x, par):
	global h
	for v in adj[x]:
		if v == par:
			continue
		num[v] = -heappop(h)
		dfs(v, x)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)
Problem p03059 (python)

Fixed submission:
a, b, c = map(int, input().split())
print((c//a)*b)

Buggy submission (verdict: Runtime Error):
a, b, c = map(int, inpuit().split())
print((c//a)*b)
Problem p03148 (python)

Fixed submission:
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
#changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if not changable:
		break

	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)


print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)

	if not changable:
		break

print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1], reverse=True)
#print(sushi)
num = 0
kind = set()
changable = []
for i in range(k):
	num += sushi[i][1]
	if sushi[i][0] in kind:
		changable.append(sushi[i][1])
	else:
		kind.add(sushi[i][0])

num += len(kind)**2
changable.reverse()
#print(changable)
ans = num

for i in range(k, n):
	if sushi[i][0] not in kind:
		num += sushi[i][1] + 2*len(kind)+1 - changable.pop()
		#print(num, kind)
		kind.add(sushi[i][0])
		ans = max(ans, num)

print(ans)
Problem p03154 (python)

Fixed submission:
MOD = 10**9 + 7
list_size = 20000001

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

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

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

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

h, w, k = map(int, input().split())
ans = k * f_list[h+w] * f_r_list[h+w-k]
ans += (h+w) * k * (k+1) * f_list[h+w-1] * f_r_list[2] * f_r_list[h+w-k]
ans %= MOD
ans += h * w * f_list[h+w-2] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k]
ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
MOD = 10**9 + 7
list_size = 200001

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

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

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

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

h, w, k = map(int, input().split())
ans = k * f_list[h+w] * f_r_list[h+w-k]
ans += (h+w) * k * (k+1) * f_list[h+w-1] * f_r_list[2] * f_r_list[h+w-k]
ans %= MOD
ans += h * w * f_list[h+w-2] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k]
ans %= MOD
print(ans)