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
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a,reverse=True)
    border=a[p-1]
    notac=0
#    temp=p-1
#    for i in range(p,n):
  #      if a[i]==border:
  #          temp=i
  #      else:
  #          break
#    temp+=1
#    print(a)
 #   print(border)
    if v<p:
        for i in range(p,n):
            if border-a[i]>m:
                notac=i
                break
    else:
        total=a[p-1]
        for i in range(p,n):

            if m*(n-v)<total-(i-p+1)*a[i]:
                notac=i
                break
            if border-a[i]>m:
                notac=i
                break
            total += a[i]
 #   print(ans)
    print(notac)











if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def check(num):
    global n, a, m, v, p
    if num >= n - 1 - p:
        return True
    idx = bisect.bisect_left(a, a[num]+m)
    sum_ = sum(a[:idx]) - a[num]
    idx -= 1
    if idx == 0:
        return True
    if a[num] + m >= math.ceil((m * min(v - (p - 1), (n - idx)) + sum_) / idx):
        return True
    else:
        return False

start = n//2
step = math.ceil(n/4)
pre_step = 0
while True:
    if pre_step == 1 and  step == 1:
        break
    if check(start):
        start -= step
    else:
        start += step
    pre_step = step
    step = math.ceil(step/2)
print(n - start - 1)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
An.sort(reverse=True)
threadhold_list = [0] * N
theard_num = An[P-1]
theard_idx = 0
sum_An = [0] * N
sum_An[0] = An[0]
for idx,val in enumerate(An):
    if theard_num == val:
        theard_idx = idx
    threadhold_list[idx] = max(0,theard_num-val)
for idx in range(1,N):
    sum_An[idx] = sum_An[idx-1] + An[idx]

#print(An)
#print(threadhold_list)
#print(sum_An)

min_num = 10**10
min_goal_num = 10**10
must_allocation_num = V- (P - 1)
for idx,val in enumerate(An):
    if idx + 1 <= P:
        min_num = min(min_num,val)
        min_goal_num = min(min_goal_num,val)
        continue
    if val == min_num:
        continue
    if threadhold_list[idx] <= M and must_allocation_num <= (N-idx):
        min_num = min(min_num,val)
        continue
    if must_allocation_num < idx:
        sum_foword_nums = sum_An[idx-1] - sum_An[must_allocation_num-1]
        allocation_diff =  must_allocation_num - (N-idx)
        diveide_allocation_num = (idx-must_allocation_num)
        plus_sum = (allocation_diff*M)
        last_num = (sum_foword_nums + plus_sum)/diveide_allocation_num
        candidate_num = An[idx] + M
        if last_num <= candidate_num:
            min_num = min(min_num,val)
            continue
    break
print(idx)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
seta = list(set(A))
count = 0
tmp = -P+(V)
if tmp > 0:
    tmp = -1
for i in range(N):
    if A[i]+M >= A[tmp]:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
N,M,V,P= map(int,input().split())
A = list(map(int,input().split()))

A.sort()
B = [0]*N
B[0] = A[0]
for i in range(1,N):
    B[i] = B[i-1] + A[i]

#print(A)
#print(B)
mn = -1 # NG
mx = N-2 # OK
k = (mn+mx)//2
while not mx-mn == 1:
    c = A[k+1]
    c += M
    p = bisect.bisect_right(A,c)
    flag = False
    #print("k",k)
    #print("c",c)
    #print("p",p)
    ALL = V*M
    ALL -= (k+1)*M # left
    ALL -= (P-1)*M # right
    if ALL <= 0:
        flag = True
    elif N-P < p:
        #print("ALL",ALL)
        #print(N-P-k,B[N-P]-B[k])
        v = V-(k+1)-(P-1)
        res = c*(N-P-k) - (B[N-P] - B[k])
        #print("res",res)
        if ALL <= res:
            flag = True
    #print("flag",flag)
    if flag:
        mx = k
    else:
        mn = k
    k = (mn+mx)//2
print(N-mx-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 + [x + M]
  b.sort()
  for i in range(V):
    if b[i] == x + M:
      return False
  return True
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 collections

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

a_count = collections.Counter(a_list)
a_count = sorted(list(a_count.items()), reverse=True)
result = 0
temp_count = 0
for i, a in enumerate(a_count):
    result += a[1]
    temp_count += a[1]
    if temp_count >= P:
        break

tail_value = a_count[i][0]
tail_num = a_count[i][1]
upper_value = tail_value * tail_num
upper_count = tail_num

for a in a_count[i+1:]:
    if upper_value - (a[0] * upper_count) <= (N-V) * M:
        result += a[1]
        upper_count += a[1]
        upper_value += a[0]*a[1]
    else:
        break

print(result)

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 + [x + M]
  b.sort()
  for i in range(V):
    if b[i] == x + M:
      return False
  return True
ok = N
ng = 0
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:
n,m,v,p = map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)

import math
def handan(a,n,m,v,p,now):
    if v<=n-now+p-1:
        if a[p-1]<=a[now]+m:
            return True
        else:
            return False
    else:
        vv=v-(n-now+p-1) #>=1
        b =a[p-1:now]
        l=len(b)
        s=sum(b)
        k_th=math.ceil((-l*a[now]+s)/(l-vv))
        if k_th<=m:
            return True
        else:
            return False
          
          
left=0
right=n-1
while left<=right:
    now = (right+left)//2
    
    if handan(a,n,m,v,p,now):
        left = now+1
    else:
        right = now-1
print(now)

Submission status: Wrong Answer

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    A.sort(reverse=True)

    I = N

    for i in range(P, N):
        if A[P-1] > A[i] + M:
            I = i
            break

    l = P-1
    r = I+1
    m = (l + r)//2

    while l + 1 != r:
        if m == N:
            print(N)
            exit()

        if m <= P - 1:
            l = m
            m = (l+r)//2
            continue

        if A[m] + M < A[P-1]:
            r = m
            m = (l+r)//2
            continue

        k = (V-P)*M - M*(N-I)
        for i in range(P-1, I):
            if i == m:
                continue
            k -= min(A[m] + M -A[i], M)
            if k < 0:
                l = m
                m = (l+r)//2
                break
        if k >= 0:
            r = m
            m = (l+r)//2

    print(l+1)











    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
#print(a)
ct=0
c=a[n-p]
d=a.index(c)
if d-(n-v)<0:
    sta=0
else:
    sta=d-(n-v)
for i in range(sta,n-p):#a.index(a[d-(n-v)])
   # if a[i]+m>=a[n-p]:
    #    ct=a.index(a[i])+1
     #   break
    if v>n-p and v+1!=n:
        if a[i]+m>=a[n-p]+m or a[i]+m>=a[v+1]:
            ct=a.index(a[i])
            break
    elif v>n-p and v+1==n:
        if a[i]+m>=a[n-p]+m:
            ct=a.index(a[i])
            break
    else:
        if a[i]+m>=a[n-p]:
            ct=a.index(a[i])
            break
#if v-1>=n-p+1:
#print(a.index(a[n-p]))
#else:
print(n-ct)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a,reverse=True)
    border=a[p-1]
    notac=0
#    temp=p-1
#    for i in range(p,n):
  #      if a[i]==border:
  #          temp=i
  #      else:
  #          break
#    temp+=1
#    print(a)
 #   print(border)
    if v<p:
        for i in range(p,n):
            if border-a[i]>m:
                notac=i
                break
    else:
        total=a[p-1]
        for i in range(p,n):
            total+=a[i]
            if m*(n-v)<total-(i-p+1)*a[i]:
                notac=i
                break
            if border-a[i]>m:
                notac=i
                break
 #   print(ans)
    print(notac)











if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().strip().split())
a=map(int,input().strip().split())
a=sorted(a,reverse=True)
minnum = a[p-1]
if n-v>=a.count(a[p-1]):
  minnum = a[p-1+a.count(a[p-1])]
if v>p:
  minnum+=m
c=p
print(a)
print(minnum)
for i in range(p,n):
  if a[i]+m >= minnum:
    c+=1
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    [n, m, v, p] = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    ans = p
    for i in range(p,n):
        tgt = a[i]
        enemy = a[p-1]
        tgt += m
        if tgt >= enemy:
            ans += 1
        else:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq

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

#print(A)

ans = 0

if P==1:
    for i in range(N):
        if A[0]<=A[i]+M:
            ans +=1
            
            
else:
    ans =P
    for i in range(P,N):
        b = (V-((P-1)+(N-i)))
        
        #print("b:{}".format(b))
        
        if b<=0:
            if A[P-1]<=A[i]+M:
                ans+=1
        else:
            Q = A[P-1:i]
            
            heapq.heapify(Q)
            target = A[i]+M
            for j in range(b*M):
                #print("Q:{}".format(Q))
                min = heapq.heappop(Q)
                heapq.heappush(Q,min+1)
            max = Q[-1]
            
            #print("max:{}".format(max))
            
            if max<=target:
                ans+=1
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect


# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

ans = 0
ok = 0
ng = 0
for i in range(n):
    if i+1 >= v:
        tmp = a[i] + m
        ind = bisect.bisect_right(a, tmp)
        if n - ind < p:
            ans += 1
    else:
        ng = -1
        ok = i

def solve(i):
        tmp = a[i] + m
        length = v - p - i
        bit = BIT(n)
        #print(i, tmp, length)
        if length <= 0:
            if a[n-p] <= tmp: 
                return True
            else:
                return False
        # 初期化
        for j in range(i+1,n-p+1):
            bit.add(j, j+1, a[j])

        times = 0
        for j in range(i+1, n-p+1)[::-1]:
            tmp_times = tmp - bit.get_val(j)
            if tmp_times < 0:
                return False
            if j+1-length <= i:
                if times >= m: 
                    return True
                else:
                    return False
            bit.add(j+1-length, j+1, tmp_times)
            times += tmp_times
        if times >= m: 
                return True
        else:
                return False

tmp_ok = ok
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
if ng == -1:
    print(ans)
else:
    print(ans + (tmp_ok - ok + 1))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_right


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()
    ret = -1

    AA = A.copy()
    for i in range(v):
        AA[i] += m
    AA.sort()

    for i in range(n):
        if n-p <= bisect_right(AA, A[i]+m):
            ret = n-i
            break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
#print(a)
ct=0
c=a[n-p]
d=a.index(c)
if d-(n-v)<0:
    sta=0
else:
    sta=d-(n-v)
for i in range(sta,n-p):#a.index(a[d-(n-v)])
   # if a[i]+m>=a[n-p]:
    #    ct=a.index(a[i])+1
     #   break
    if v>n-p and v+1!=n:
        if a[i]+m>=a[n-p]+m or a[i]+m>=a[v+1]:
            ct=a.index(a[i])+1
            break
    elif v>n-p and v+1==n:
        if a[i]+m>=a[n-p]+m:
            ct=a.index(a[i])+1
            break
    else:
        if a[i]+m>=a[n-p]:
            ct=a.index(a[i])+1
            break
#if v-1>=n-p+1:
#print(a.index(a[n-p]))
#else:
print(n-ct+1)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
  N, M, V, P = map(int, input().split())
  Al = list(map(int, input().split()))
  A = sorted(Al, reverse=True)
  
  cnt = 0
  
  B = A[P:]
  B.reverse()
  for i in range(M):
    tmp = V-P+1
    if(tmp < 0):
      continue
    for j in range(tmp):
      B[j] += 1
    B.sort()
      
  edge = B[-1]
  Ap = A[P:]
  
  for Ai in A:
    if( Ai + M >= edge ):
      cnt += 1
  
  print(cnt)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
# 0 ~ (p-1) は問題に選ばれる可能性が既にある（数が同じならそれ以降も）
# その他で逆転できるのはどれか
ans = [0] * n
for i in range(p):
    ans[i] = 1

index = p # まだ定まっていないもの
for i in range(p, n):
    if a[i] == a[p-1]:
        ans[i] = 1
        index += 1
    else:
        break

if index == n:
    print(sum(ans))
    exit()

# 選ばれていない中で最大: a[index]
# 選ばれている中で最小: a[index-1] => a[p-1] と考えることに修正
mn = a[p-1]

# 0 ~ (index-2)の index-1個 は必ず選ぶ。index-1は選ばない
# 残り、v - (index-1 + 1) 個をどう選ぶか

# 簡単な場合を先に処理
if v - (p-1) + 1 <= 0:
    for i in range(p, n):
        if a[i] + m >= mn:
            ans[i] = 1
        else:
            break
    print(sum(ans))
    exit()

# 小さいものにもvoteする必要がある場合（v - (index-1 + 1))個

# それより大きいものが何個あるかを求めておく
# それ以下のものも把握しておく（それ以下のものには何個配っても良い）:

large = [0] * n
small = [0] * n
for i in range(p, n):
    if i == p:
        large[p] = 0
        small[p] = n - 1 - p
    else:
        if a[i] == a[i-1]:
            large[i] = large[i-1]
            small[i] = small[i-1]
        else:
            large[i] = i - p
            small[i] = n - 1 - i


acum = [0] * (n+1)
for i in range(p, n):
    acum[i+1] = acum[i] + a[i]

for i in range(p, n):
    unvote = v - (p-1 + 1) - small[i]
    if unvote <= 0:
        if a[i] + m >= mn:
            ans[i] = 1
    else:
        if a[i] + m < mn:
            break
        # 分配する個数 large[i] -> index ~ index + large[i] - 1
        sm = acum[p + large[i]] - acum[p]
        if sm + unvote * m <= (a[i] + m) * large[i]:
            ans[i] = 1

print(sum(ans))

Submission status: Wrong Answer

Solution code:
def examA():
    N, A, B = LI()
    ans = inf
    if abs(A-B)%2==0:
        ans = abs(A-B)//2
    cur = min((A+B-1)//2,(2*N-A-B+1)//2)
    ans = min(ans,cur)
    print(ans)
    return

def examB():
    N, M, V, P = LI()
    A = LI(); A.sort()
    maxA = A[N-P]
    sumA = maxA*(N-P)-sum(A[:N-P])
#    print(maxA,sumA)
    l = -1; r = N-P
    while(r-l>1):
        flag = True
        now = (l+r)//2
        c = sumA - (maxA-A[now])
        need = maxA - A[now]
        if need>M:
            flag = False
        if (V-P)*M-(N-P)*(M-need)>c:
            flag = False
        if flag:
            r = now
        else:
            l = now
#        print(A[now],c,(V-P)*M,need)
    ans = N-r
    print(ans)
    return

def examC():
    N = I()
    ans = [["."]*N for _ in range(N)]
    if N%3!=0 and N%4!=0:
        print("-1")
        return
    if N%3==0:
        for i in range(N//3):
            ans[i*3][i*3] = "a"
            ans[i*3][i*3+1] = "a"
        for i in range(N//3):
            ans[i*3+1][i*3+2] = "a"
            ans[i*3+2][i*3+2] = "a"
    else:
        for i in range(N//2):
            if i%2==0:
                for j in range(N // 4):
                    ans[i * 2][j * 4] = "a"
                    ans[i * 2][j * 4 + 1] = "a"
                    ans[i * 2 + 1][j * 4] = "b"
                    ans[i * 2 + 1][j * 4 + 1] = "b"
                for j in range(N // 4):
                    ans[i*2 +2][j*4] = "c"
                    ans[i*2 +3][j*4] = "c"
                    ans[i*2 +2][j*4 +1] = "d"
                    ans[i*2 +3][j*4 +1] = "d"
            if i%2==1:
                for j in range(N // 4):
                    ans[i * 2][j * 4+2] = "a"
                    ans[i * 2][j * 4 +3] = "a"
                    ans[i * 2 +1][j * 4+2] = "b"
                    ans[i * 2 +1][j * 4 +3] = "b"
                for j in range(N // 4):
                    ans[i*2-2][j*4+2] = "c"
                    ans[i*2-1][j*4+2] = "c"
                    ans[i*2-2][j*4 +3] = "d"
                    ans[i*2-1][j*4 +3] = "d"
    for v in ans:
        print("".join(map(str,v)))
    return

def examD():
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    N, M, V, P = MI()
    A = MI()
    # N, M, V, P = 10**5, 10*19, 10**4, 10**4
    # A = [i for i in range(N)]
    A = sorted(A, reverse=True)
    AH = A[:P]
    AH_min = AH[-1]
    AT = []
    for i in range(P, N):
        if AH_min == A[i]:
            AH.append(A[i])
        else:
            AT.append(A[i])
    # print(AH, AT)
    # print('M=', M, 'V=', V)
    ans = len(AH)
    AT_len = len(AT)

    if len(AT) <= V - len(AH) + 1:
        # print(len(AT), V - len(AH) + 1)
        for i in range(AT_len):
            if AH_min == AT[i]:
                ans += 1
        print(ans)
    else:
        _V = V - len(AH) + 1
        # print(_V, V, AH_min)
        for i in range(AT_len):
            if AH_min <= (AT[i] + M):
                remaining = AT_len - (i + 1)
                # print(i, remaining, _V, AH_min, AT[i] + M, AH_min >= (AT[i] + M))
                if remaining + 1 >= _V:
                    ans += 1

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
  N, M, V, P = map(int, input().split())
  Al = list(map(int, input().split()))
  A = sorted(Al, reverse=True)
  
  cnt = 0
  
  B = A[P:]
  B.reverse()
  for i in range(M):
    tmp = V-P+1
    if(tmp < 0):
      continue
    for j in range(tmp):
      B[j] += 1
    B.sort()
      
  print(A)
  print(B)
  edge = B[-1]
  Ap = A[P:]
  
  for Ai in A:
    if( Ai + M >= edge ):
      cnt += 1
  
  print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import bisect


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m, v, p = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    mi = (n - v) * m
    cor_v = 10 ** 20
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        pp = bisect.bisect_right(a, bin_v)
        b = True
        for i in range(pp + 1, n):
            if a[i] > bin_v:
                if cost + a[i] - bin_v <= mi:
                    cost += a[i] - bin_v
                else:
                    if n - i + 1 >= p:
                        inc_v = bin_v
                        b = False
                        break
                    else:
                        break
        if b:
            cor_v = bin_v
    cnt = 0
    for v in a:
        if v >= cor_v:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def examA():
    N, A, B = LI()
    ans = inf
    if abs(A-B)%2==0:
        ans = abs(A-B)//2
    cur = min((A+B-1)//2,(2*N-A-B+1)//2)
    ans = min(ans,cur)
    print(ans)
    return

def examB():
    N, M, V, P = LI()
    A = LI(); A.sort()
    maxA = A[N-P]
    sumA = maxA*(N-P)-sum(A[:N-P])
#    print(maxA,sumA)
    l = -1; r = N-P
    while(r-l>1):
        flag = True
        now = (l+r)//2
        c = sumA - (maxA-A[now])
        need = maxA - A[now]
        if need>M:
            flag = False
        if (V-P)*M-(N-P)*(M-need)>=c:
            flag = False
        if flag:
            r = now
        else:
            l = now
#        print(A[now],c,(V-P)*M,need)
    ans = N-r
    print(ans)
    return

def examC():
    N = I()
    ans = [["."]*N for _ in range(N)]
    if N%3!=0 and N%4!=0:
        print("-1")
        return
    if N%3==0:
        for i in range(N//3):
            ans[i*3][i*3] = "a"
            ans[i*3][i*3+1] = "a"
        for i in range(N//3):
            ans[i*3+1][i*3+2] = "a"
            ans[i*3+2][i*3+2] = "a"
    else:
        for i in range(N//2):
            if i%2==0:
                for j in range(N // 4):
                    ans[i * 2][j * 4] = "a"
                    ans[i * 2][j * 4 + 1] = "a"
                    ans[i * 2 + 1][j * 4] = "b"
                    ans[i * 2 + 1][j * 4 + 1] = "b"
                for j in range(N // 4):
                    ans[i*2 +2][j*4] = "c"
                    ans[i*2 +3][j*4] = "c"
                    ans[i*2 +2][j*4 +1] = "d"
                    ans[i*2 +3][j*4 +1] = "d"
            if i%2==1:
                for j in range(N // 4):
                    ans[i * 2][j * 4+2] = "a"
                    ans[i * 2][j * 4 +3] = "a"
                    ans[i * 2 +1][j * 4+2] = "b"
                    ans[i * 2 +1][j * 4 +3] = "b"
                for j in range(N // 4):
                    ans[i*2-2][j*4+2] = "c"
                    ans[i*2-1][j*4+2] = "c"
                    ans[i*2-2][j*4 +3] = "d"
                    ans[i*2-1][j*4 +3] = "d"
    for v in ans:
        print("".join(map(str,v)))
    return

def examD():
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

Solution code:
n, m, v, p = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

mi = 0
ma = n-1

def isok(i):
    if i+p>=n:
        return True
    b = a.copy()
    count = v
    for j in range(max(0, i-v+1), i+1):
        b[j] += m
        count-=1
    j = n - 1
    for _ in range(p-1):
        if count == 0:
            break
        b[j] += m
        j -= 1
        count-=1
    k = j
    if count>0:
        s = m*count
        for j in range(i + 1, k + 1):
            s += b[j]
        for j in range(i + 1, k + 1):
            b[j] = s // (k - i)
        for j in range(i + 1, i+1+s % (k - i)):
            b[j] +=1
    me = b[i]
    b.sort()
    for j in range(n):
        if j == n - 1:
            break
        if b[j + 1] > me:
            break
    return j+p>=n

while mi != ma:
    mii = (mi + ma) // 2
    if isok(mii):
        ma = mii
    else:
        mi = mii + 1
print(n-mi)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
seta = list(set(A))
count = 0
tmp = -P-(N-1-V)
if tmp < -(len(seta)):
    tmp = 0
for i in range(N):
    if A[i]+M >= seta[tmp]:
        print(A[i]+M,seta[tmp])
        count += 1
print(count-2)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
for i in range(v):
  b[i]+=m
b = sorted(b, reverse=True)
c = b[p-1]
d = [n+m for n in a]
print(len([i for i in d if i >= c]))