Problem:


Score : 700 points

Problem Statement

N problems are proposed for an upcoming contest. Problem i has an initial integer score of A_i points.

M judges are about to vote for problems they like. Each judge will choose exactly V problems, independently from the other judges,
and increase the score of each chosen problem by 1.

After all M judges cast their vote, the problems will be sorted in non-increasing order of score, and the first P problems will be chosen for the problemset.
Problems with the same score can be ordered arbitrarily, this order is decided by the chief judge.

How many problems out of the given N have a chance to be chosen for the problemset?

Constraints

2 \le N \le 10^5

1 \le M \le 10^9

1 \le V \le N - 1

1 \le P \le N - 1

0 \le A_i \le 10^9

Input

Input is given from Standard Input in the following format:

N M V P
A_1 A_2 ... A_N

Output

Print the number of problems that have a chance to be chosen for the problemset.

Sample Input 1

6 1 2 2
2 1 1 3 0 2

Sample Output 1

5

If the only judge votes for problems 2 and 5, the scores will be 2 2 1 3 1 2.
The problemset will consist of problem 4 and one of problems 1, 2, or 6.

If the only judge votes for problems 3 and 4, the scores will be 2 1 2 4 0 2.
The problemset will consist of problem 4 and one of problems 1, 3, or 6.

Thus, problems 1, 2, 3, 4, and 6 have a chance to be chosen for the problemset. On the contrary, there is no way for problem 5 to be chosen.

Sample Input 2

6 1 5 2
2 1 1 3 0 2

Sample Output 2

3

Only problems 1, 4, and 6 have a chance to be chosen.

Sample Input 3

10 4 8 5
7 2 3 6 1 6 5 4 6 5

Sample Output 3

8



Sample input:
6 1 2 2
2 1 1 3 0 2


Sample output:
5

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
           
right = P-1
left = N

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
    
    print("r:{}".format(right))
    print("l:{}".format(left))
    print("i:{}".format(i))   
        
    if b<0:
        if A[P-1]<=target:
            right = i
        else:
            left = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)


def can_be_used(x):
    # x: 0-index
    if x < p:
        return True

    if a[x] + m < a[p-1]:
        return False

    vote_max = (p - 1 + n - x) * m
    for i in range(p-1, x):
        vote_max += a[x] + m - a[i]

    if vote_max < m * v:
        return False

    return True


l = 0
r = n - 1

while r - l > 1:
    mid = (l + r) // 2

    if can_be_used(mid):
        l = mid
    else:
        r = mid

ans = l + 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
bb = sorted(list(set(a)))
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    cnt = 0
    for ind,item in enumerate(a):
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    if cnt >= m*v:
        return True
    else:
        return False

ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-mid)

Submission status: Wrong Answer

Solution code:
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

A2 = A[i_X:(P-2):-1]

# A_X can adopt?
NG_POINT = (P-1) * M
NG_POINT += (N - i_X - 1) * M
MV = M * V
ans = 0
last = -1

for i in range(len(A2)):
    A_X = A2[i]

    if last == A2[i]:
        NG_POINT += M
        continue

    total = M + NG_POINT

    for j in range(i+1, len(A2)):
        total += A_X + M - A2[j]

    if total >= MV:
        ans = i
        break
    else:
        NG_POINT += M
        last = A_X

print(i_X+1-ans)

Submission status: Wrong Answer

Solution code:
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

A2 = A[i_X:(P-2):-1]

# A_X can adopt?
NG_POINT = (P-1) * M
NG_POINT += (N - i_X - 1) * M
MV = M * V
ans = 0

for i in range(len(A2)):
    A_X = A2[i]
    total = M + NG_POINT

    for j in range(i+1, len(A2)):
        total += A_X + M - A2[j]

    if total >= MV:
        ans = i
        break
    else:
        NG_POINT += M

print(i_X+1-ans)

Submission status: Wrong Answer

Solution code:
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 = defaultdict(int)
ACN = defaultdict(int)
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])

Submission status: Wrong Answer

Solution code:
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]

print(1)
exit()


# 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])

Submission status: Wrong Answer

Solution code:
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)

print(1)
exit()


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])

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)
#3 2 2 1 1 0

e = len([x for x in a if a[p] <= x + m])

ans = p

for i in range(e - 1, p - 1, -1):
    if sum([a[i] + m - x for x in a[p - 1:i]]) >= m * (v - (p + n - i - 1)):
        ans = i + 1
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

b = [a[x] for x in range(n - p)]

total = sum(b)

vote=(v - p) * m

ans = p
if len(b) > 1:
    for n, i in enumerate(b):
        if (total - i + vote) // (len(b) - 1) <= i + m:
            ans += len(b) - n
            break

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

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

def check(N, M, V, P, As, i):
    # As = 3 2 2 1 1 0
    border = As[P - 1]
    a = As[i]
    # iはTop Pに入っている
    if a >= border:
        return True
    # iに全票入れてもTop Pに入れない
    if a + M < border:
        return False

    # iがTop Pに入るのを保てる最大の票数を計算
    num = M  # i番目に全票
    num += (P - 1) * M  # Top 1からP-1までには全票いれてよい
    num += (N - i - 1) * M # iよりあとのものにも全票いれてよい
    for j in range(P, i): # 同票まではOK
        num += (a + M - As[j])
    
    return num >= M * V


def solve(N, M, V, P, As):

    As = As[:]
    As.sort(reverse=True)

#    for j in range(N):
#        print("j, check = ", j, check(N, M, V, P, As, j))

    # 二分探索がなりたたない場合を除外
    if check(N, M, V, P, As, N-1):
        return N

    ok = 0
    ng = N - 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(N, M, V, P, As, mid):
            ok = mid
        else:
            ng = mid

    return ok + 1


print(solve(N, M, V, P, As))
#print(solve_slow(N, M, V, P, As))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    if cnt >= m*v:
        return True
    else:
        return False

ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-mid)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
bb = sorted(list(set(a)))
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + u_cnt >= v-1:
        return True
    cnt = 0
    for ind,item in enumerate(a):
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    if cnt >= m*v:
        return True
    else:
        return False

ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-mid)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(l, r):
    if r-l <= 1:
        return r
    m = (l+r)//2
    if P+m >= V and A[m]+M >= A[N-P]:
        return f(l, m)
    elif P+m >= V:
        return f(m, r)
    else:
        num = M*(V-P-m)
        i = m+1
        while i < N-P and num > 0:
            num -= A[m]+M-A[i]
            i += 1
        if num > 0:
            return f(m, r)
        else:
            return f(l, m)

m = f(0, N-P)
if P+m >= V and A[m]+M >= A[N-P]:
    f = True
elif P+m >= V:
    f = False
else:
    num = M*(V-P-m)
    i = m+1
    while i < N-P and num > 0:
        num -= A[m]+M-A[i]
        i += 1
    if num > 0:
        f = False
    else:
        f = True

if f:
    m -= 1

ans = N-m-1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(l, r):
    if r-l <= 1:
        return l
    m = (l+r)//2
    if P+m >= V and A[m]+M >= A[N-P]:
        return f(l, m)
    elif P+m >= V:
        return f(m, r)
    else:
        num = M*(V-P-m)
        i = m+1
        while i < N-P and num > 0:
            num -= A[m]+M-A[i]
            i += 1
        if num > 0:
            return f(m, r)
        else:
            return f(l, m)
        
ans = N-f(0, N-P)-1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(l, r):
    if r-l <= 1:
        return l
    m = (l+r)//2
    if P+m >= V and A[m]+M >= A[N-P]:
        return f(l, m)
    elif P+m >= V:
        return f(m, r)
    else:
        num = M*(V-P-m)
        i = m+1
        while i < N-P and num > 0:
            num -= A[m]+M-A[i]
            i += 1
        if num > 0:
            return f(m, r)
        else:
            return f(l, m)
        
ans = N-f(0, N-1)-1
print(ans)

Submission status: Wrong Answer

Solution code:
from inspect import currentframe

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    C = sorted_dic_A[P:]

    num_vote = M * V
    a = 0
    b = len(C)
    flag = True
    while a < b:
        def is_margin_plus(i):
            v = C[i][1]
            margin = num_vote
            margin -= M * (P-1)
            margin_list = [v+M-w for (j,w) in C if j!=i]
            mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
            margin -= M
            margin -= sum(mod_margin_list)
            # print("margin: {}".format(margin))

            return margin > 0

        i = (a + b) // 2
        # input()
        # print("(a, i, b): ({}, {}, {})".format(a, i, b))

        if is_margin_plus(i):
            # print('is_margin_plus: {}'.format(True))
            b = i
        else:
            # print('is_margin_plus: {}'.format(False))
            a = i + 1
            flag = False

    ans = a + P + 1 if flag else (a + P)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from inspect import currentframe

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    C = sorted_dic_A[P:]

    num_vote = M * V
    a = 0
    b = len(C)
    flag = True
    while a < b:
        def is_margin_plus(i):
            v = C[i][1]
            margin = num_vote
            margin -= M * (P-1)
            margin_list = [v+M-w for (j,w) in C if j!=i]
            mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
            margin -= M
            margin -= sum(mod_margin_list)
            # print("margin: {}".format(margin))

            return margin > 0

        i = (a + b) // 2
        # input()
        # print("(a, i, b): ({}, {}, {})".format(a, i, b))

        if is_margin_plus(i):
            # print('is_margin_plus: {}'.format(True))
            b = i
        else:
            # print('is_margin_plus: {}'.format(False))
            a = i + 1
            flag = False

    ans = a + P + 1 if flag else (a + P)
    ans = a + P
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from inspect import currentframe

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    C = sorted_dic_A[P:]

    num_vote = M * V
    a = 0
    b = len(C)
    flag = True
    while abs(b - a) > 1:
        def is_margin_plus(i):
            v = C[i][1]
            margin = num_vote
            margin -= M * (P-1)
            margin_list = [v+M-w for (j,w) in C if j!=i]
            mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
            margin -= M
            margin -= sum(mod_margin_list)
            # print("margin: {}".format(margin))

            return margin > 0

        i = (a + b) // 2
        # input()
        # print("(a, i, b): ({}, {}, {})".format(a, i, b))

        if is_margin_plus(i):
            # print('is_margin_plus: {}'.format(True))
            b = i
        else:
            # print('is_margin_plus: {}'.format(False))
            a = i
            flag = False

    ans = a + P + 1 if flag else (a + P)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(idx):
    if idx <= p:
        return True
    if a[idx]+m < a[p]:
        return False

    vote = (n+p-idx)*m
    for i in range(p, idx):
        vote += descA[idx]+m - descA[i]
    if vote > m*v:
        return True
    else:
        return False

n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
descA = sorted(a, reverse=True)

ok = -1
ng = n
while ok+1 < ng:
    md = (ok+ng)//2
    if check(md):
        ok = md
    else:
        ng = md

print(ok+1)

Submission status: Wrong Answer

Solution code:
def check(idx):
    if idx <= p:
        return True
    if a[idx]+m < a[p]:
        return False

    vote = 0
    vote += (p-1)*m
    vote += (n-idx)*m
    for i in range(p, idx):
        vote += descA[idx]+m - descA[i]
    if vote < m*v:
        return False
    else:
        return True


n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
descA = sorted(a, reverse=True)

ok = -1
ng = n
while ok+1 < ng:
    md = (ok+ng)//2
    if check(md):
        ok = md
    else:
        ng = md

print(ok+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)
d = dd(int)
for x in a: d[x] += 1
#print(d)
ks = sorted(d.keys())
#print(ks)
def check(x):
  b = a + []
  isit = 0
  t = 0
  for i in range(V):
    if isit == 0 and x == b[i]:
      b[i] = -float("inf")
      isit = 1
  b.sort()
  for k in ks:
    if k > x: break
    t += d[k] * M
  #t += M * (P - 1)
  p = (x + M > b[-1])
  c = 0
  for i in range(N - 1, 0, -1):
    if x <= b[i] < x + M: 
      if p <= P - 1: t += M
      else: t += min(M, x + M - b[i])
    if c != b[i]:
      c = b[i]
      p += 1
      if p >= P and (c > x + M):
        return False
  #print(x, t, b, V * M)

  return t >= V * M
ok = N
ng = -1
m = (ok + ng) // 2
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(a[m]):
    ok = m
  else: ng = m
print(N - ok)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)
d = dd(int)
for x in a: d[x] += 1
#print(d)
ks = sorted(d.keys())
#print(ks)
def check(x):
  b = a + []
  isit = 0
  t = 0
  for i in range(V):
    if isit == 0 and x == b[i]:
      b[i] = -float("inf")
      isit = 1
  b.sort()
  for k in ks:
    if k > x: break
    t += d[k] * M
  #t += M * (P - 1)
  p = (x + M > b[-1])
  c = 0
  for i in range(N - 1, 0, -1):
    if x <= b[i] < x + M: 
      if p <= P - 1: t += M
      else: t += min(M, x + M - b[i])
    if c != b[i]:
      c = b[i]
      p += 1
      if p >= P and (c > x + M):
        return False
  #print(x, t, b, V * M)

  return t >= V * M
ok = N
ng = -1
m = (ok + ng) // 2
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(a[m]):
    ok = m
  else: ng = m
res = N
ng -= 1
if N <= 10:
  for i in range(N - 1):
    if check(a[i]) == False:
      ng = max(ng, a[i])
    #print(a[i], check(a[i]), ng)
for k in ks:
  if k <= ng: res -= d[k]
print(res)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n
low = 0
mid = (high + low) // 2
f = True


for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

while low < high:
    mid = (low + high) // 2

    if mid <= p-1:
        f = True
    else:
        if prob_set[mid] + m < prob_set[p - 1]:
            f = False
        else:
            hyou = m * (p - 1) \
                   + m * (n - mid) \
                   + (prob_set[mid] + m) * (mid - p + 1) \
                   - (ruiseki_prob[mid-1] - ruiseki_prob[p-2])
            # まず0 ~ p-2まで(1,2,,,p-1まで) :p-1
            # 次にmid,mid+1,,,n-1まで       :n-mid
            # 上限はp-1,p,,,mid-1は(mid)+mずつ
            # 和はmid-1 - p-2
            if hyou < m*v:
                f = False
            else:
                f = True
    if f:
        low = mid + 1
    else:
        high = mid

print(high)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう
# あるiについて評価するとき,以下の観点に注意する

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse= True)

def check(i):
  if i <= P-1:
    return True
  vote = (V-1)*M
  vote -= (N-1-i)*M
  vote -= (P-1)*M
  if vote <= 0:
    return A[i]+M >= A[P-1]
  else:
    return sum(A[P-1:i])+vote <= (A[i]+M)*(i-(P-1))

ok = -1
ng = N
while(ok+1 < ng):
  md = (ok+ng)//2
  if check(md):
    ok = md
  else:
    ng = md
print(ok+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m,v,p = map(int,readline().split())
lis = np.array(read().split(),np.int64)



lis.sort()

def test(i):
    if n-i <= p:
        return True

    num = lis[i] + m
    li = np.zeros(n,np.int64)
    li = num-lis
    li = np.minimum(li,m)
    li[n-p+1:] = m
    if(li < 0).any():
        return False
    li[i] = 0
    x = li.sum()
    return li.sum() >= m * (v-1)

low = -1
high = n-1

while low +1 < high:
    mid = (low + high) // 2
    if test(mid):
        low = mid
    else:
        high = mid

ans = n-high

print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n
low = 0
mid = (high + low) // 2
# 下げるときはhigh = mid-1
# 上げるときはlow = mid
for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

# print(prob_set)
# print(ruiseki_prob)

while low < high:
    mid = (low + high) // 2
    # print(mid)
    f = True
    # まず上からp個以内であれば問答無用でOK (つまりindexがp>i)
    if mid < p:
        # print("<p")
        f = True
    else:
        # i~nには全員が票を投じると考えてよい (ここまででn-i票)
        # 次に上からp-1個に全員が票をいれてもよい(ここまでn-i + p-1)
        # それでも無理ならp ~ i-1までに残りを入れる必要がある.これがp[i] + m以下であればいいことがわかる
        if prob_set[mid] + m < prob_set[p - 1]:
            # どうあがいても無理
            # print("too short")
            f = False
        else:
            hyou = m * (p - 1) \
                   + m * (n - mid) \
                   + (prob_set[mid] + m) * (mid - (p - 1)) \
                   - (ruiseki_prob[mid-1] - ruiseki_prob[p-2])
            if hyou < m*v:
                f = False
            else:
                f = True
    if f:
        low = mid + 1
    else:
        high = mid

print(low)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう
# あるiについて評価するとき,以下の観点に注意する

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True) + [-10 ** 10]
L, R, sA, lP = 0, N, [A[P - 1]], A[P - 1]
for i in range(P, N):
    sA.append(sA[-1] + A[i])

while R - L > 1:
    mid = L + (R - L) // 2
    if mid < P:
        L = mid
    elif A[mid] + M <= A[P - 1]:
        R = mid
    else:
        mi = mid - P + 1
        if M * (N - mi) + (A[mid] + M - 1) * (mi + 1) - sA[mi] >= M * V:
            L = mid
        else:
            R = mid
print(L + 1)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n
low = 0
mid = (high + low) // 2
# 下げるときはhigh = mid-1
# 上げるときはlow = mid
for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

# print(prob_set)
# print(ruiseki_prob)

while low < high:
    mid = (low + high) // 2
    # print(mid)
    f = True
    # まず上からp個以内であれば問答無用でOK (つまりindexがp>i)
    if mid < p:
        # print("<p")
        f = True
    else:
        # i~nには全員が票を投じると考えてよい (ここまででn-i票)
        # 次に上からp-1個に全員が票をいれてもよい(ここまでn-i + p-1)
        # それでも無理ならp ~ i-1までに残りを入れる必要がある.これがp[i] + m以下であればいいことがわかる
        if prob_set[mid] + m < prob_set[p - 1]:
            # どうあがいても無理
            # print("too short")
            f = False
        else:
            # どうにかなる
            if (p - 1) + (n - mid) >= v:
                # print("OK for voting")
                f = True
            else:
                # mid
                amari_hyou = m * (v - (p - 1) - (n - mid))
                if ruiseki_prob[mid - 1] - ruiseki_prob[p - 2] + amari_hyou <= (prob_set[mid] + m) * (
                        (mid - 1) - (p - 2)):
                    # print("OK for super-voting")
                    f = True
                else:
                    # print("cannot EVEN super-voting")
                    f = False
    if f:
        low = mid + 1
    else:
        high = mid


print(low)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう
# あるiについて評価するとき,以下の観点に注意する

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

target = A[p-1]
target_count = 0

for a in A:
    if a == target:
        target_count += 1
    elif a < target:
        break

over_target = p - 1
prev = target
ans = p
total = 0

for idx in range(p, n):
    candidate = A[idx]
    under = n - idx - 1
    if candidate == prev:
        ans += 1
        total += candidate
        continue

    if candidate + m >= target:
        if over_target + under >= v-1:
            ans += 1
            prev = candidate
            total += candidate

        else:
            exceed = abs(v-1 - under - over_target) * m
            possible = (candidate+m) * (idx-p) - total
            if exceed <= possible:
                ans += 1
                prev = candidate
                total += candidate
            else:
                break

    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n
low = 0
mid = (high + low) // 2
# 下げるときはhigh = mid-1
# 上げるときはlow = mid
for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

# print(prob_set)
# print(ruiseki_prob)

while low < high:
    mid = (low + high) // 2
    # print(mid)
    f = True
    # まず上からp個以内であれば問答無用でOK (つまりindexがp>i)
    if mid < p:
        # print("<p")
        f = True
    else:
        # i~nには全員が票を投じると考えてよい (ここまででn-i票)
        # 次に上からp-1個に全員が票をいれてもよい(ここまでn-i + p-1)
        # それでも無理ならp ~ i-1までに残りを入れる必要がある.これがp[i] + m以下であればいいことがわかる
        if prob_set[mid] + m < prob_set[p - 1]:
            # どうあがいても無理
            # print("too short")
            f = False
        else:
            # どうにかなる
            if p - 1 + n - mid >= v:
                # print("OK for voting")
                f = True
            else:
                # mid
                amari_hyou = m * (v - (p - 1) - (n - mid))
                if ruiseki_prob[mid - 1] - ruiseki_prob[p - 2] + amari_hyou <= (prob_set[mid] + m) * (
                        (mid - 1) - (p - 2)):
                    # print("OK for super-voting")
                    f = True
                else:
                    # print("cannot EVEN super-voting")
                    f = False
    if f:
        low = mid + 1
    else:
        high = mid


print(low)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう
# あるiについて評価するとき,以下の観点に注意する