Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
n,k = map(int, input().split())
a = []
for i in range(n):
    a.append(int(input()))
a.reverse()
# dp[i] := i番目の数字から始めたときの最大値
dp = [0 for i in range(n)]
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
#阪堺区間に注意
dp[0] = 1
update(a[0], 1)
max_a = max(a) + 1
for i in range(1,n):
    # print("{} {}".format(max(a[i]-k, 0), min(max_a, a[i]+k+1)))
    dp[i] = query(max(a[i]-k, 0), min(max_a, a[i]+k+1)) + 1
    update(a[i], dp[i])
print(max(dp))

Fixed submission:

n,k = map(int, input().split())
a = []
for i in range(n):
    a.append(int(input()))
a.reverse()
# dp[i] := i番目の数字から始めたときの最大値
dp = [0 for i in range(n)]
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

max_a = 300020
#####単位元######
ide_ele = 0
num =2**(max_a-1).bit_length()
seg=[ide_ele]*(2*num - 1)
#阪堺区間に注意
dp[0] = 1
update(a[0], 1)
for i in range(1,n):
    # print("{} {}".format(max(a[i]-k, 0), min(max_a, a[i]+k+1)))
    dp[i] = query(max(a[i]-k, 0), min(max_a, a[i]+k+1)) + 1
    update(a[i], dp[i])
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)

Fixed submission:
n, k = map(int, input().split())
span = []
mod = 998244353
for i in range(k):
    span.append(list(map(int, input().split())))
dp = [0 for i in range(n+1)]
acc = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(n+1):
    acc[i] += acc[i-1]
    acc[i] %= mod
    dp[i] += acc[i]
    for j in range(k):
        l, r = span[j]
        if l + i < n + 1:
            acc[l + i] += dp[i]
        if r + 1 + i < n + 1:
            acc[r+1 + i] -= dp[i]
    dp[i] %= mod
print(dp[-2] % mod)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
for i in range(1, n+1):
    ans = 0
    for x in range(1, int(i**0.5)+1):
        for y in range(1,int(i**0.5)+1):
            if -2*x*y - (3 * x**2) - (3 * y**2) + 4*i >= 0:
                if (-(y + x) + (-2*x*y - (3 * x**2) - (3 * y**2) + 4*i)**0.5) % 2 == 0 and (-(y + x) + (-2*x*y - (3 * x**2) - (3 * y**2) + 4*i)**0.5) / 2 >= 1:
                    ans += 1
            else:
                break
    print(ans)

Fixed submission:
n = int(input())
ans = [0 for i in range(n + 1)]
for x in range(1,int(pow(n, 0.5)+1)):
    for y in range(1,int(pow(n, 0.5)+1)):
        for z in range(1,int(pow(n, 0.5)+1)):
            if x**2 + y**2+z**2 +x*y + x*z + y*z <= n:
                ans [x**2 + y**2+z**2 +x*y + x*z + y*z] += 1
for i in range(1,n+1):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
d = int(input())
c = list(map(int, input().split()))
score = []
for i in range(d):
    score.append(list(map(int, input().split())))
last_day = [0 for i in range(26)]
k = 0
for i in range(d):
    ans = 0
    max_score = -10**9
    for j in range(1, 27):
        s = score[i][j-1]
        for k in range(1,27):
            if j == k:
                continue
            else:
                s -= c[k-1] * (d - i+1 - last_day[k-1])
        if s > max_score:
            ans = j
            max_score = s
    last_day[ans] = i+1
    print(ans)
    k += max_score

Fixed submission:
d = int(input())
c = list(map(int, input().split()))
score = []
for i in range(d):
    score.append(list(map(int, input().split())))
for i in range(d):
    print(score[i].index(max(score[i])) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * (n-1):
        break
print(" ".join(map(str, a)))


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * n:

        break
print(" ".join(map(str, a)))
Buggy python submission (verdict: Runtime Error):
Vt = input()
print(t.replace("?", "D"))

Fixed submission:
t = input()
print(t.replace("?", "D"))
Buggy python submission (verdict: Runtime Error):
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[]
now=0
for i in range(n+1):
        ans.append(a[now])
        now=a[now]-1
#print(ans)

ans2=collections.Counter(ans)

ac=ans2.most_common()[0][0]
#print(ac)
index=-1
index2=-1

for i in range(len(ans)):
    if ans[i]==ac:
        if index==-1:        
            index=i
        else:
            index2=i
assert(index2 == -1)
#print(index,index2)
#print((k-index-1)%(index2-index))
if k < index:
    print(ans[k])
else:
    print(ans[(k-index-1)%(index2-index)+index])



Fixed submission:
import sys
sys.setrecursionlimit(10**6)
n,k = map(int, input().split())
a = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n):
    adjacent_list[i+1].append(a[i])
finished = set()
route = []
def dfs(node):
    finished.add(node)
    route.append(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
dfs(1)
if len(route) > k:
    print(route[k])
else:
    index = route.index(adjacent_list[route[-1]][0])
    k -= index
    route = route[index:]
    print(route[k % len(route)])

Buggy python submission (verdict: Runtime Error):
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[1]
now=0
passed = set()
for i in range(n+1):
    if a[now] in passed:
        ans.append(a[now])
        break
    else:
        ans.append(a[now])
        passed.add(a[now])
        now=a[now]-1
#print(ans)
#変更
passed = set()
index = ans[:-1].index(ans[-1])
index_1 = len(ans)-2
#print(index)
#print(index_1)
print(ans[(k-index-1)%(index_1-index)+index])



Fixed submission:
import sys
sys.setrecursionlimit(10**6)
n,k = map(int, input().split())
a = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n):
    adjacent_list[i+1].append(a[i])
finished = set()
route = []
def dfs(node):
    finished.add(node)
    route.append(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
dfs(1)
if len(route) > k:
    print(route[k])
else:
    index = route.index(adjacent_list[route[-1]][0])
    k -= index
    route = route[index:]
    print(route[k % len(route)])
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
n,m,k = map(int, input().split())
mod = 998244353
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
combi = [0 for i in range(n)]
combi[0] = 1
combi[1] = n-1
for i in range(2,n):
    combi[i] = (combi[i-1]*(n-i)*mod_inv(i,mod)) % mod
for i in range(k+1):
    plus = m * pow(m-1,n-1-i,mod)
    plus *= combi[n-i-1]
    plus %= mod
    ans += plus
    ans %= mod
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
n,m,k = map(int, input().split())
mod = 998244353
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
combi = [0 for i in range(n)]
combi[0] = 1
for i in range(1,n):
    combi[i] = (combi[i-1]*(n-i)*mod_inv(i,mod)) % mod
for i in range(k+1):
    plus = m * pow(m-1,n-1-i,mod)
    plus *= combi[n-i-1]
    plus %= mod
    ans += plus
    ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
x = int(input())
start = int(pow(x,0.2))
for i in range(-1000,1000+1):
    k = pow(x + pow(i,5),0.2)
    k = round(k,7)
    if pow(int(k),5) - pow(i,5) == x:
        print(int(k),i)
        exit()





Fixed submission:
x = int(input())
for i in range(-1000,1000+1):
    for j in range(-1000,1001):
        if pow(i,5) - pow(j,5) == x:
            print("{} {}".format(i,j))
            exit()

Buggy python submission (verdict: Runtime Error):
x = int(input())
start = int(pow(x,0.2))+1
for i in range(-start,start):
    k = pow(x + pow(i,5),0.2)
    k = round(k,6)
    if type(k) != type(1+1j) and pow(int(k),5) - pow(i,5) == x:
        print(int(k),i)
        exit()





Fixed submission:
x = int(input())
for i in range(-1000,1000+1):
    for j in range(-1000,1001):
        if pow(i,5) - pow(j,5) == x:
            print("{} {}".format(i,j))
            exit()
Buggy python submission (verdict: Runtime Error):
n,a,b,c = map(int, input().split())
ans = []
number = dict()
number['A'] = a
number['B'] = b
number['C'] = c
query = [input() for i in range(n)]
for i in range(n):
    s = query[i]
    s_1, s_2 = s[0], s[1]
    if number[s_1] == 0 and number[s_2] == 0:
        print("No")
        exit()
    else:
        if number[s_1] > number[s_2]:
            number[s_1] -= 1
            number[s_2] += 1
            ans.append(s_2)
        elif number[s_1] < number[s_2]:
            number[s_2] -= 1
            number[s_1] += 1
            ans.append(s_1)
        else:
            if i == n-1:
                number[s_2] -= 1
                number[s_1] += 1
                ans.append(s_1)
            else:
                if query[i+1] == s_1 + s_2:
                    number[s_2] -= 1
                    number[s_1] += 1
                    ans.append(s_1)
                else:
                    n_1,n_2 = query[i+1]
                    if s_1 in set(n_1,n_2):
                        number[s_2] -= 1
                        number[s_1] += 1
                        ans.append(s_1)
                    else:
                        number[s_1] -= 1
                        number[s_2] += 1
                        ans.append(s_2)

    #print("A:{} B:{} C:{}".format(number['A'],number['B'],number['C']))
print("Yes")
for i in range(n):
    print(ans[i])

Fixed submission:
n,a,b,c = map(int, input().split())
ans = []
number = dict()
number['A'] = a
number['B'] = b
number['C'] = c
query = [input() for i in range(n)]
for i in range(n):
    s = query[i]
    s_1, s_2 = s[0], s[1]
    if number[s_1] == 0 and number[s_2] == 0:
        print("No")
        exit()
    else:
        if number[s_1] > number[s_2]:
            number[s_1] -= 1
            number[s_2] += 1
            ans.append(s_2)
        elif number[s_1] < number[s_2]:
            number[s_2] -= 1
            number[s_1] += 1
            ans.append(s_1)
        else:
            if i == n-1:
                number[s_2] -= 1
                number[s_1] += 1
                ans.append(s_1)
            else:
                if query[i+1] == s_1 + s_2:
                    number[s_2] -= 1
                    number[s_1] += 1
                    ans.append(s_1)
                else:
                    n_1,n_2 = query[i+1]
                    if s_1 in set([n_1,n_2]):
                        number[s_2] -= 1
                        number[s_1] += 1
                        ans.append(s_1)
                    else:
                        number[s_1] -= 1
                        number[s_2] += 1
                        ans.append(s_2)

    #print("A:{} B:{} C:{}".format(number['A'],number['B'],number['C']))
print("Yes")
for i in range(n):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
11 10 9

Fixed submission:
def fn(x):
    return ((a*x)//b) - a*(x//b)
a,b,n = map(int, input().split())
ans = 0
if b <= n:
    ans = b-1
else:
    ans = n
print(fn(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import copy
n = int(input())
a = list(map(int, input().split()))
array = [(a[i], i+1) for i in range(n)]
array.sort(reverse=True)
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    for j in range(n):
        if i + j >= n:
            break
        count = i + j
        #右に移した場合
        value, index = array[count]
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + value * abs((n - j) - index))
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + value * abs((i + 1) - index))
ans = 0
for i in range(n+1):
    for j in range(n+1):
        ans = max(ans, dp[i][j])
print(ans)
        




Fixed submission:
import copy
n = int(input())
a = list(map(int, input().split()))
array = [(a[i], i+1) for i in range(n)]
array.sort(reverse=True)
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    for j in range(n):
        if i + j >= n:
            break
        count = i + j
        #右に移した場合
        value, index = array[count]
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + value * abs((n - j) - index))
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + value * abs((i + 1) - index))
ans = 0
for i in range(n+1):
    for j in range(n+1):
        ans = max(ans, dp[i][j])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
k = int(input())
ans = []
def bfs(que):
    finished = set()
    while que and len(ans) <= 10**6:
        x = que.popleft()
        ans.append(int(x))
        if x not in finished:
            finished.add(x)
            p = int(x[-1])
            que.append(x + str(p))
            if 1 <= p <= 8:
                que.append(x + str(p+1))
                que.append(x + str(p-1))
            elif p == 0:
                que.append(x + str(p+1))
            else:
                que.append(x + str(p-1))
que = deque([])
for i in range(1,10):
    que.append(str(i))
bfs(que)
ans.sort()
print(ans[k-1])

Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
k = int(input())
ans = []
def bfs(que):
    finished = set()
    while que and len(ans) <= 10**5:
        x = que.popleft()
        ans.append(int(x))
        if x not in finished:
            finished.add(x)
            p = int(x[-1])
            if 1 <= p <= 8:
                que.append(x + str(p-1))
                que.append(x + str(p))
                que.append(x + str(p+1))
            elif p == 0:
                que.append(x + str(p))
                que.append(x + str(p+1))
            else:
                que.append(x + str(p-1))
                que.append(x + str(p))
que = deque([])
for i in range(1,10):
    que.append(str(i))
bfs(que)
ans.sort()
print(ans[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
#色が変わるところでコスト
inf = 10**9
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
adjacent_list = [[] for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        if i == (h-1) and j == (w-1):
            continue
        if j != (w-1):
            if grid[i][j] != grid[i][j+1] and grid[i][j] == '#':
                adjacent_list[w*i + (j + 1)].append([w*(i) + (j + 2), 1])
            else:
                adjacent_list[w*i + (j + 1)].append([w*(i) + (j + 2), 0])
        if i != (h-1):
            if grid[i][j] != grid[i+1][j] and grid[i][j] == '#':
                adjacent_list[w*i + (j + 1)].append([w*(i + 1) + (j + 1), 1])
            else:
                adjacent_list[w*i + (j + 1)].append([w*(i + 1) + (j + 1), 0])
finished = set()
def dfs(node,cost):
    finished.add(node)
    for i in adjacent_list[node]:
        dist[i[0]] = min(dist[i[0]],dist[node] + i[1])
        dfs(i[0],i[1])
dist = [inf for i in range(h*w+1)]
dist[1] = 0
dfs(1,0)
if grid[-1][-1] == '#':
    dist[-1] += 1
print(dist[-1])



Fixed submission:
import sys
sys.setrecursionlimit(10**6)
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
#色が変わるところでコスト
inf = 10**9
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
adjacent_list = [[] for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        if i == (h-1) and j == (w-1):
            continue
        if j != (w-1):
            if grid[i][j] != grid[i][j+1] and grid[i][j] == '#':
                adjacent_list[w*i + (j + 1)].append([w*(i) + (j + 2), 1])
            else:
                adjacent_list[w*i + (j + 1)].append([w*(i) + (j + 2), 0])
        if i != (h-1):
            if grid[i][j] != grid[i+1][j] and grid[i][j] == '#':
                adjacent_list[w*i + (j + 1)].append([w*(i + 1) + (j + 1), 1])
            else:
                adjacent_list[w*i + (j + 1)].append([w*(i + 1) + (j + 1), 0])
finished = set()
def dfs(node,cost):
    finished.add(node)
    for i in adjacent_list[node]:
        if dist[node] + i[1] < dist[i[0]]:
            dist[i[0]] = dist[node] + i[1]
            dfs(i[0],i[1])
dist = [inf for i in range(h*w+1)]
dist[1] = 0
dfs(1,0)
if grid[-1][-1] == '#':
    dist[-1] += 1
print(dist[-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
reverse_now = 0
first = ""
latter = ""
for i in range(q):
    k = list(input().split())
    if k[0] == "1":
        reverse_now = 1 - reverse_now
    else:
        f,c = k[1], k[2]
        if f == "1" and reverse_now == 0:
            first = c + first
        if f == "1" and reverse_now == 1:
            latter = latter + c
        if f == "2" and reverse_now == 0:
            latter = latter + c
        if f == "2" and reverse_now == 1:
            first = c + first
if reverse_now == 1:
    ans = list(first + s + latter)
    ans.reverse()
    ans = "".join(ans)
else:
    ans = first + s + latter
print(ans)




Fixed submission:
s = input()
q = int(input())
reverse_now = 0
first = ""
latter = ""
for i in range(q):
    k = list(input().split())
    if k[0] == "1":
        reverse_now = 1 - reverse_now
    else:
        f,c = k[1], k[2]
        if f == "1" and reverse_now == 0:
            first = c + first
        if f == "1" and reverse_now == 1:
            latter += c
        if f == "2" and reverse_now == 0:
            latter +=  c
        if f == "2" and reverse_now == 1:
            first = c + first
if reverse_now == 1:
    ans = list(first + s + latter)
    ans.reverse()
    ans = "".join(ans)
else:
    ans = first + s + latter
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
ans = ["-1" for i in range(n)]
for i in range(m):
    s, c = input().split()
    s = int(s)
    if s == 1 and c == '0':
        print(-1)
        exit()
    if ans[s-1] == "-1":
        ans[s-1] = c
    else:
        if ans[s-1] != c:
            print(-1)
            exit()
if ans[0] == '-1':
    ans[0] = 1
print(("".join(ans)).replace("-1","0"))


Fixed submission:
n, m = map(int, input().split())
ans = ["-1" for i in range(n)]
for i in range(m):
    s, c = input().split()
    s = int(s)
    if s == 1 and c == '0' and n != 1:
        print(-1)
        exit()
    if ans[s-1] == "-1":
        ans[s-1] = c
    else:
        if ans[s-1] != c:
            print(-1)
            exit()
if ans[0] == '-1':
    ans[0] = "1"
if m == 0:
    ans[n-1] = "0"
print(("".join(ans)).replace("-1","0"))
Buggy python submission (verdict: Runtime Error):
import itertools
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
ans = p
a.sort(reverse=True)
def binary_search(left, right):
    if right - left <= 1:
        return left
    middle = (left + right) // 2
    if check(middle):
        return binary_search(middle, right)
    else:
        return binary_search(left, middle)

def check(target):
    used_vote = (p + n - target - 1) * m
    sum_vote = 0
    for i in range(target-1, p-2, -1):
        sum_vote += (a[target] + m) - a[i]
    if sum_vote >= m * v - used_vote: 
        return True
    else:
        return False

print(binary_search(0,n+1) + 1)

Fixed submission:
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def binary_search(left, right):
    if right - left <= 1:
        return left
    middle = (left + right) // 2
    if check(middle):
        return binary_search(middle, right)
    else:
        return binary_search(left, middle)

def check(target):
    used_vote = (p + n - target - 1) * m
    sum_vote = 0
    for i in range(target-1, p-2, -1):
        if a[target] + m < a[i]:
            return False
        sum_vote += (a[target] + m) - a[i]
    if sum_vote >= (m * v - used_vote): 
        return True
    else:
        return False
print(binary_search(0,n) + 1)

Buggy python submission (verdict: Runtime Error):
n ,a, b = map(int, input().split())
dis = b - a
if dis % 2 == 0:
    print(dis // 2)
else:
    shiftR = (n-b)
    shiftL = (a-1)
    ans = min(n-a,b-1, shiftR + 1 + ((n - (a + 1) + shiftR) //2), shiftL + 1 + (((b - 1) - shiftL - 1) // 2))
    print(ans)

Fixed submission:
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def binary_search(left, right):
    if right - left <= 1:
        return left
    middle = (left + right) // 2
    if check(middle):
        return binary_search(middle, right)
    else:
        return binary_search(left, middle)

def check(target):
    used_vote = (p + n - target - 1) * m
    sum_vote = 0
    for i in range(target-1, p-2, -1):
        if a[target] + m < a[i]:
            return False
        sum_vote += (a[target] + m) - a[i]
    if sum_vote >= (m * v - used_vote): 
        return True
    else:
        return False
print(binary_search(0,n) + 1)