Problem p02824 (python)

Fixed submission:
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


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

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

# A_P -> A_X (A_P - M = A_X)
A_P = A[P-1]
A_X = A[P]
i_X = P
for i in range(P, len(A)):
    if (A_P - A[i]) > M:
        A_X = A[i-1]
        i_X = i-1
        break
    elif i == (len(A)-1):
        A_X = A[i]
        i_X = i
    else:
        continue

NG_POINT = (P-1) * M


def isPossible(i):
    if (i+1) < P:
        return True
    elif i > i_X:
        return False

    MV = M * V
    ax = A[i]
    score = ax + M

    total = M + NG_POINT
    total += (N - i - 1) * M

    for j in range(i-1, P-2, -1):
        total += score - A[j]

    #print("i", i, "total", total, "NG_POINT", NG_POINT)

    if total >= MV:
        return True

    return False


left = 0
right = i_X

if not isPossible(left):
    print(1)
    exit()

if isPossible(i_X):
    print(i_X + 1)
    exit()

#print("A", A, "i_X", i_X)

for _ in range(i_X):
    #print("left", left, isPossible(left), "right", right, isPossible(right))
    if (left + 1) == right:
        break

    mid = (left + right) // 2

    if isPossible(mid):
        left = mid
    else:
        right = mid

print(left + 1)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

#NUM = [0] * N
#ACN = [0] * N
NUM = {}
ACN = {}
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    if d in NUM:
        NUM[d] += 1
    else:
        NUM[d] = 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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


NUM = [0] * N
#ACN = [0] * N
ACN = {}
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt


# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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


NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

print(1)
exit()
    
# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

print(1)
exit()

    
# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        
print(1)
exit()


#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

print(1)
exit()

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]


for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# calc p
p = P
for i in range(0, A[0]):

    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        p = i
        break

if p < 0:
    print(N)
    exit()

#print("p", p)
#print("NUM", NUM)


R = p + M
if R < 0:
    R = A[0] - A[len(A)-1]

ans = R
NG = N - ACN[R]
PNG = (N - ACN[R]) * M
m = M

#print("R", R)

'''
# PNG
for i in range(R+1, A[N-1]):
    if NUM[i] == 0:
        continue

    if M < (i-R):
        PNG += (N - ACN[i-1]) * M
        break

    PNG += NUM[i] * (i-R)
    NG_notall[(i-R)] = NUM[i]
'''

# loop
for r in range(R, -1, -1):
    m = M
    t = NUM[r]

    if t == 0:
        continue

    sm = M * V

    #print("r", r, "sm", sm, "PNG", PNG, "NUM", NUM[r])

    sm -= (r - p)*NUM[r]
    sm -= PNG
    m -= (r - p)

    if sm < 0:
        ans = r
        break

    rn = r
    for q in range(r-1, -1, -1):
        tq = NUM[q]
        if tq == 0:
            continue

        #t += tq

        if q < p:
            m -= (rn - q)

        if m < 0:
            PNG += NUM[r] * M
            break

        sm -= (rn - q) * t

        #print("q", q, "m", m, "sm", sm, "rn-q", (rn-q), "t", t)

        rn = q
        t += tq

        if sm < 0:
            ans = r
            break

    if sm < 0:
        ans = r
        break

    #print("sm", sm, "m", m)

    if m < 0:
        continue

    pr = p
    for j in range(len(NUM)):
        if NUM[j] == 0:
            continue

        pr -= NUM[j]
        sm -= NUM[j] * (M - j)

        if pr < 0:
            break

    if sm < 0:
        ans = r
        break
    else:
        PNG += NUM[r] * M


# print(ans)
print(ACN[r])

'''
    for q in range(p-1, -1, -1):
        tq = NUM[q]
        if tq == 0:
            continue

        t += tq
        sm -= (q - rn) * t
        rn = q

        if sm < 0:
            ans = r
            break
'''