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:
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 M < threadhold_list[idx]:
        print(idx)
        exit(0) 
    if (N-idx) < must_allocation_num:
        sum_foword_nums = sum_An[idx-1] - sum_An[(P - 1-1)]
        allocation_diff =  must_allocation_num - (N-idx)
        diveide_allocation_num = (idx-(P - 1))
        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
    print(idx)
    exit(0)
print(N)

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 M < threadhold_list[idx]:
        continue 
    if (N-idx) < must_allocation_num:
        sum_foword_nums = sum_An[idx-1] - sum_An[(P - 1-1)]
        allocation_diff =  must_allocation_num - (N-idx)
        diveide_allocation_num = (idx-(P - 1))
        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
    print(idx)
    exit(0)
print(N)

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()]
p-=1

a.sort(reverse=True)

ans=0
s = sum(a)

def safe(index):
    if a[p]>a[index]+m:
        return False
    i=0
    wall = -1
    while a[i]>=a[index]+m:
        if a[i]>=a[index]+m+1:
            wall = i
        i+=1
    if i>index:
        return True
    intg = 0
    while i<index:
        intg += a[index] + m - a[i]
        i+=1
    intg += (len(a)-1-index)*m + min(v,p)*m
    #print("intg = ",intg ,m*(v-1) )
    return intg >= m*(v-1)

left = 0
right = len(a)-1
ans = int((right - left)/2)
if safe(right):
    ans = right
else:
    j = safe(ans)
    while not(j and not safe(ans+1)):
        if j:
            left = ans
        else:
            right = ans
        ans = left + int((right - left)/2)
        j = safe(ans)
print(ans+1)
"""
for i in range(len(a)):
    print(a[i],safe(i))
"""

Submission status: Wrong Answer

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

a = sorted(a)

sm = sum(a[:n-p+1])

for k in range(n-p):
    sm -= a[k]
    if (n-p-k)*(a[k]+m) - sm +(p+k)*m < v*m:
        continue
    else:
        print(n-k)
        exit()

print(p)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
pre = list(map(int, input().split()))
li = sorted(pre)
total = M * V
for i in range(N):
	if li[i] + M >= li[-P]:
		tmp = i+1 + P - 1
		nokori = total - (M * tmp)
		if N - tmp != 0:
			if li[i] + M > nokori // (N-tmp) + li[-P]:
				ans = N - i
				break
		else:
			ans = N-1
			break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
B = sorted(A,reverse=True)
X = P-1
C = B[X:]
V = V-X
P = P-X
D = list(set(C))
D = [i for i in D if i >= D[len(D)-1]-M]
Y = []
for i in D:
    F = M*(V-(len(C)-C.index(i)))
    E = C[:C.index(i)]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        break
Z = B.index(i)+C.count(i)
print(Z)

Submission status: Wrong Answer

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

S = tuple(reversed(sorted(A))) #O(N)

cnt = 0
sum_memo = {}
su = 0
b = 0
b_rank = 0

for n, i in enumerate(S): # Loop O(N)
    if b != i:
        n_rank = n+1
        rank = n
    else: 
        rank = b_rank
    b = i
    b_rank = rank
    if n >= P - 1:
        su += S[n]
        sum_memo[n] = su
    
    if P > rank:
        cnt += 1
    else:
        xx = P-1 + N - rank
        if xx < V:
            if rank in sum_memo.keys():
                sum_val = sum_memo[rank]
            else:
                sum_val = sum(S[P-1:rank])
                sum_memo[rank] = sum_val
            x = max(math.ceil((sum_val+(V-xx)*M)/(rank-P+1)), S[P-1])
        else:
            x = S[P-1]
                    
        y = i + M
        if x <= y:
            cnt += 1
        else:
            break
print(cnt)

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 M < threadhold_list[idx]:
        break 
    if (N-idx) < must_allocation_num:
        sum_foword_nums = sum_An[idx-1] - sum_An[(P - 1-1)]
        allocation_diff =  must_allocation_num - (N-idx)
        diveide_allocation_num = (idx-(P - 1))
        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
if idx == N - 1:
    print(N)
else:
    print(idx)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
B = sorted(A,reverse=True)
X = B.index(B[P-1])
C = B[P-1:]
V = V-X
P = P-X
D = list(set(C))
D = [i for i in D if i >= D[len(D)-1]-M]
Y = []
for i in D:
    F = M*(V-(len(C)-C.index(i)))
    E = C[:C.index(i)]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        break
Z = B.index(i)+C.count(i)
print(Z)

Submission status: Wrong Answer

Solution code:
def main():
    n, m, v, p = list(map(int, input().split()))
    a = sorted(list(map(int, input().split())))
    # print(a)

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-2:]
        # print(b)
        if b[0] < 0:
            return False
        rest = v-n+len(b)
        if rest <= 0:
            return False
        # print(rest)

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        #print(d, e)
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    # print(value(2))

    print(n-b_search(0, n-1, value))


main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

a = sorted(a)

sm = sum(a[:n-p+1])
mxcnt = a[:n-p+1].count(a[n-p])
mx = a[n-p]

if v <= p:
    k = bisect_left(a,mx - m)
    print(n-k)
    exit()

for k in range(n-p):
    sm -= a[k]
    if (n-p-k)*(a[k]+m) - sm +(p+k)*m < v*m:
        continue
    else:
        print(n-k)
        exit()

print(p)

Submission status: Wrong Answer

Solution code:
import bisect

n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
b = list(reversed(a))

def ok(i):
  if i < p:
    return True
  elif a[i]+m < a[p]:
    return False
  else:
    can = a[i]+m
    c = bisect.bisect_right(b,a[i])
    must = m*(v-(p-1+c))
    for j in range(p-1,n-c):    
      must -= can-a[j] 
    if must > 0:
      return False
    else:
      return True
    
L = 0
U = n
while U-L > 1:
  mid = (L+U)//2
  if ok(mid):
    L = mid
  else:
    U = mid

print(U)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m, v, p = MAP()
a = LIST()
a = sorted(a, reverse=True)
def hantei(i):
    if i < p: return True
    if a[p-1] > a[i] + m: return False
    if i <= n-v+p-1: return True
    if (i-p+1)*(a[i]+m)-sum(a[p-1:i]) >= m*(v-p-n+i+1): return True
    return False

right = n-1
left = 0

while right-left > 1:
    mid = (right+left)//2
    if hantei(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Wrong Answer

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

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

def isSelectable(pointer):
  if max(aList[p-1:pointer]) - aList[pointer - 1] > m:
    return False
  subListSum = sum(aList[p-1:pointer])
  if subListSum - aList[pointer - 1] * (pointer - (p - 1)) > (n - v) * m: # = なら OK
    return False
  return True

pointer = (n + p) // 2
preNum = 0
while preNum == pointer:
  preNum = pointer
  if isSelectable(pointer):
    pointer = (n + pointer) // 2
  else:
    pointer = (p + pointer) // 2

print(aList.index(aList[pointer]) + aList.count(aList[pointer]))

Submission status: Wrong Answer

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


ans = P
S = A[P-1]
for i in range(P, N):
    if A[i]+M < A[P-1]:
        continue
    if V <= P-1+N-i:
        if A[i]+M >= A[P-1]:
            ans += 1
    else:
        if S+M*(V-P+1-N+i)//(i-(P-1)) <= (A[i]+M):
            ans += 1
    S += A[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
bbn=1000000007
	
#+++++

class mmm:
	def __init__(self):
		self.n, self.m, self.v ,self.p = map(int, input().split())
		self.al=list(map(int, input().split()))
		self.al.sort(reverse=True)
		r=0
		m=self.al[0]
		self.diffl=[0]*self.n
		for i,v in enumerate(self.al):
			r+=m-v
			self.diffl[i]=r
		self.border=self.al[self.p-1]
			
		pa(self.diffl)
		pa(self.al)
	
	def is_ok(self,ni):
		if ni <= self.p-1:
			return True
		vv=self.al[ni]
		if vv + self.m < self.border:
			return False
		
		nv=self.v-((self.p-1)+(self.n-ni))
		if nv <= 0:
			return True
		
		ss=nv*self.m
		di=self.diffl[ni]-self.diffl[self.p-1]

		div=self.al[0]-self.border
		din=di-(div*(ni-1))
		pa((ni,di,din,div))
		
		if din > ss:
			return True
		return False
	
	
	def solve(self):
		ok=0
		if self.is_ok(self.n-1):
			return self.n
		ng=self.n-1
		
		while ng-ok>=2:
			mm=(ng+ok)//2
			if self.is_ok(mm):
				ok=mm
			else:
				ng=mm
			#print(ok,ng,mm)
		return ok+1

		
def main():
	a=mmm()
	ret=a.solve()
	print(ret)
	
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def check(x,N,M,V,P,A):
    if (N-x)<=P:
        return True
    if(V<=x+P):
        return(A[x]+M>=A[N-P])

    x_score = A[x]+M
    total_v = (V-x-P)*M

    for i in range(x+1,N-P+1):
        total_v -= min(M,(x_score - A[i]))
    if total_v <= 0:
        return True
    else:
        return False

def main():
    N,M,V,P = map(int,input().split())
    A = [int(x) for x in input().split()]
    A.sort()

    if(check(0,N,M,V,P,A)):
        print(N)
        return

    isOK = N-1
    isNG = 0
    while(isOK-isNG>1):
        middle = (isOK+isNG)//2
        if(check(middle,N,M,V,P,A)):
            isOK = middle
        else:
            isNG = middle
    print(N-isOK)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep = ' ', end = '\n'):
    print(*var, file=sys.stderr, end = end, sep = sep)

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, m, val, p = I()
a = I()
v = [0] * n
for i in range(n):
    a[i] = [a[i], i]
a.sort()
ans = p
# print(*[i for i, j in a])
if p >= n:
    ans = n
else:
    for i in range(p):
        v[a[i][1]] = 1
    now = p
    while now < n and a[now][0] == a[p-1][0]:
        v[a[now][1]] = 1
        ans += 1
        now += 1
    now -= 1
    if val <= now:
        for i in range(now, now - val, -1):
            a[i][0] += m
    else:
        for i in range(min(n, val)):
            a[i][0] += m
    a.sort()
    # print(*[i for i, j in a])

    for i in range(p):
        if not v[a[i][1]]:
            ans += 1
    now = p
    while now < n and a[now][0] == a[p-1][0]:
        if not v[a[now][1]]:
            ans += 1
        now += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n,m,v,p = map(int, input().split())
a = [int(i) for i in input().split()]
b = []
c = 0
for i in a:
    b.append([c, i])
    c += 1

b.sort(key = lambda x:-1*x[1])
cand = b[p:]
d = 0
if v > n - p:
    amari = v - n + p
else:
    amari = 0
    
for j in cand:
    if j[1] + m >= b[p - 1][1] + amari:
        d += 1
    
print(p + d)

Submission status: Wrong Answer

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

N,M,V,P = map(int,input().split())
A = sorted([int(i) for i in input().split()])
MINMAXA = A[N-P]

answer = 0
while A:
    tmp = A.pop()
    if tmp >= MINMAXA:
        if tmp > MINMAXA and V > 1:
            V -= 1
        answer += 1
    else:
        A.append(tmp)
        break

if V == 1:
    for i in range(len(A))[::-1]:
        if A[i] + M >= MINMAXA:
            answer += 1
        else:
            break
    print(answer)

else:
    if len(A) < V:
        print(answer)
    else:
        for _ in range(len(A) - V + 2):
            tmp = A.pop()
            if tmp + M >= MINMAXA:
                answer += 1
            else:
                break
        print(answer)

Submission status: Wrong Answer

Solution code:
temp = list(map(int,input().split()))
n = temp[0]
m = temp[1]
v = temp[2]
p = temp[3]
count = 0

a = list(map(int,input().split()))
new = sorted(a)
b = new[n-p]
i = 0
while i < n-p:
  new[i] = new[i] + m
  i = i + 1

j = 0
if v <= n-p:  
  while j < n-p:  
    if new[j] >= b:
      count = count+1
    j = j + 1
else:
  newnew = sorted(new)
  count = v-p
  while j < n-v:
    if newnew[j] == newnew[n-v]:
      count = count + 1
    j = j + 1
    
print(count+p)

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

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

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

if check(0):
    print(n)

for i in range(n-1):
    if not check(i) and check(i+1):
        print(n - i - 1)
        exit()

Submission status: Wrong Answer

Solution code:
import collections
x = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()],reverse=True)
n, m, v, p = x[0], x[1], x[2], x[3]
a_ = collections.Counter(a)
ans = 0
i = 0
while ans < p:
    ans += a_[a[i]]
    i = ans
l = a[:ans]
r = a[ans:]
l_r = l[-1]
l_r_cnt = a_[l_r]
if v <= ans - l_r_cnt + 1:
    for i in r:
        if l_r <= m + i:
            ans += 1
else:
    res = v - (ans - l_r_cnt + 1)
    cnt = l[-l_r_cnt:]
    for i in range(len(r)):
        can = m + r[i]
        if l_r <= can:
            if res <= len(r) - (i + 1):
                ans += 1
            else:
                res2 = res - (len(r) - (i + 1))
                if (sum(cnt) + res2 * m) // len(cnt) <= r[i] + m:
                    ans += 1
        cnt.append(r[i])
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())
n += 1
v += 1
a = [-10**20] + list(map(int, input().split()))
a = sorted(a)

def solve(i):
        tmp = a[i] + m
        if i+1 >= v:
            ind = bisect.bisect_right(a, tmp)
            if n - ind < p:
                return True
        if i+1 >= n-p:
            return True
  
        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 False
        else:
                return True

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


def vote(scores, org_score, voted_score, n, m, v, p):
    if len(scores[scores > org_score]) < p:
        return True

    fix = len(scores[scores > voted_score])
    if fix > p:
        return False

    remain = m * (v-1)
    if remain < 1:
        return True
    
    # 採用が確定している上位には投票しても問題ない
    remain -= m * fix
    if remain < 1:
        return True
    
    # 元の点が自分以下ならば投票しても問題ない
    remain -= (len(scores[scores <= org_score])-1) * m
    if remain < 1:
        return True

    xyz = scores[(scores > org_score) & (scores < voted_score)]
    for v in xyz:
        diff = voted_score - v
        remain -= diff

        if remain < 1:
            return True

    if remain < len(xyz):
        return True
    return False


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

sscore = np.array(sorted(scores))
thres1 = sscore[-p] # 最低でもこの値を超えないと上位になれない

uscore = sorted(list(set(scores)))

# binary search
# 上位pに入れる最小値を探す
low = 0
high = len(uscore)-1
while low < high:
    mid = (low + high) // 2

    tgt = uscore[mid]
    if (tgt + m) < thres1:
        low = mid+1
        continue
    if vote(sscore, tgt, tgt+m, n, m, v, p):
        high = mid
    else:
        low = mid+1

threshold = uscore[high]

print(len(sscore[sscore >= threshold]))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M,V,P = [int(i) for i in input().split()]
A_ = [int(i) for i in input().split()]

A = sorted(A_)
in_A = set(A)
#print(A)
#print(A[0])
#print(A[N-V])

count = 0
for i in range(N):
    #print(A[i],A[(i+N-V)%N])
    if A[(i+N-V)%N] < A[-P]:
        count += 1
        continue
    else:
        l = A[(i+N-V)%N] - A[i]
        if l <= M:
            break

print(N - count)

Submission status: Wrong Answer

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

def main():
    N, M, V, P = (int(x) for x in input().split())
    A = [int(x) for x in input().split()]
    
    A.sort(reverse=True)
    c = collections.Counter(A)
    picked = A[:P]

    for i in range(P,N):
        tail = (N-i)
        
        if tail >= V:
            if A[i]+M >= A[P-1]:
                picked.append(A[i])
        else:
            over = V - tail
            if over <= (P-1):
                if A[i]+M >= A[P-1]:
                    picked.append(A[i])
            else:
                miwariate_point = (over-(P-1))*M
                btw = A[P-1:i]
                base = miwariate_point//len(btw)
                amari = miwariate_point%len(btw)
                if btw[0] >= (btw[-amari]+1):
                    rival = btw[0] + base
                else:
                    rival = btw[-amari] + base + 1
                    
                if A[i]+M >= rival:
                    picked.append(A[i])
    ok = list(set(picked))
    ans = 0
    for x in ok:
        ans += c[x]
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()

    boarder = A[N - P]
    simple = max(V - P, 0)
    h, l = N , -1
    while h - l  > 1:
        m = (h + l) // 2
        canChose = False
        if m >= simple:
            if A[m] + M >= boarder: canChose = True
        else:
            if simple - m >= N - P - simple:
                NG_boarder = A[m] + M
                pointer = N - P
                used = [0] * (N - P - m)
                count = 0
                width = simple - m
                for i in reversed(range(width - 1, N - P - m)):
                    canuse = NG_boarder - (A[N - P - i] + used[i])
                    for j in range(width): used[i - j] += canuse
                    count += canuse
                if count >= M: canChose = True

        if canChose: h = m
        else: l = m

    print(N - l - 1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

N,M,V,P = map(int,input().split())
A = sorted([int(i) for i in input().split()])
print(A)
MINMAXA = A[N-P]

answer = 0
while A:
    tmp = A.pop()
    if tmp >= MINMAXA:
        if tmp > MINMAXA and V > 1:
            V -= 1
        answer += 1
    else:
        A.append(tmp)
        break

if V == 1:
    for i in range(len(A))[::-1]:
        if A[i] + M >= MINMAXA:
            answer += 1
        else:
            break
    print(answer)

else:
    if len(A) < V:
        print(answer)
    else:
        for _ in range(len(A) - V + 1):
            tmp = A.pop()
            if tmp + M >= MINMAXA:
                answer += 1
            else:
                break
        print(answer + 1)

Submission status: Wrong Answer

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

left=0
right=n-p-1

while  right -left >1:
    mid =(left+right)//2
    if a[mid]+m < a[n-p]:
        left=mid+1
    else:
        j=v-(mid+1+p-1)
        if j <= 0:
            right=mid
        else:
            sum=0
            for k in range(mid+1,n-p+1,1):
                if m+a[mid]-a[k] < 0:
                    left = mid+1
                    break
                sum+=a[mid]+m-a[k]
                if sum >= j*m:
                    right=mid
                    break
                if k==n-p:
                    left=mid+1

if left==right:
    print(n-left)
elif right-left==1:
    p1 = 0
    mid = left
    if a[mid] + m < a[n - p]:
        p1 = 0
    else:
        j = v - (mid + 1+p-1)
        if j <= 0:
            p1 = 1
        else:
            sum = 0
            for k in range(mid + 1, n+p+1, 1):
                if m + a[mid] - a[k] < 0:
                    p1 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p1 = 1
                    break
                if k == n-p:
                    p1 = 0
    p2 = 0
    mid = right
    if a[mid] + m < a[n - p]:
        p2 = 0
    else:
        j = v - (mid + 1 + p - 1)
        if j <= 0:
            p2 = 1
        else:
            sum = 0
            for k in range(mid + 1, n + p + 1, 1):
                if m + a[mid] - a[k] < 0:
                    p2 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p2 = 1
                    break
                if k == n - p:
                    p2 = 0

    if p1==1:
        print(n-left)
    elif p2==1:
        print(n-left-1)
    else:
      	print(n-left-2)

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)]
    MAP = {}
    A = sorted(A, reverse=True)
    AH = A[:P]
    AH_min = AH[-1]
    AT = []
    cur = 0
    sent_c = 0
    for i in range(P, N):
        if AH_min == A[i]:
            sent_c += 1
        # else:
        if A[i] not in MAP:
            MAP[A[i]] = cur
        cur += 1
        AT.append(A[i])
    # print(AH, AT)
    # print('M=', M, 'V=', V)
    ans = len(AH)
    AT_len = len(AT)
    # print(AT, MAP)
    # show(len(AT), V - len(AH) + 1)

    if len(AT) <= V - len(AH) + 1:
        # print(len(AT), V - len(AH) + 1)
        print(ans + sent_c)
    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 - (MAP[AT[i]] + 1)
                # print(i, remaining, _V, AH_min, 'MAP', MAP[AT[i]])
                if remaining + 1 >= _V:
                    ans += 1

        print(ans + sent_c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
b = list(reversed(a))

def ok(i):
  if i < p:
    return True
  else:
    can = a[i]+m
    c = bisect.bisect_right(b,a[i])
    must = m*(v-(p-1+c))
    for j in range(p-1,n-c):    
      must -= can-a[j] 
    if must > 0:
      return False
    else:
      return True
    
L = 0
U = n
while U-L > 1:
  mid = (L+U)//2
  if ok(mid):
    L = mid
  else:
    U = mid

print(U)