Submission #9180982


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M,V,P = map(int,readline().split())
A = np.array(read().split(),np.int64)

A.sort()

def test(i):
    """
    i 番の人を勝者にできる
    """
    # はじめから上位P以内の場合
    if N - i <= P:
        return True
    # 他人に入ることを許容できる票数を計算する
    me = A[i] + M
    C = np.zeros(N,np.int64)
    C = me - A
    C = np.minimum(C,M)
    C[N-P+1:] = M # この層は負け前提
    if (C < 0).any():
        return False
    C[i] = 0
    x = C.sum()
    return C.sum() >= M * (V-1)

left = -1 # 勝てない
right = N-1 # 勝てる
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = N - right
print(answer)

Submission Info

Submission Time
Task B - Voting Judges
User maspy
Language Python (3.4.3)
Score 700
Code Size 912 Byte
Status AC
Exec Time 375 ms
Memory 21528 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 60
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt, 01-56.txt, 01-57.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 375 ms 21528 KB
00-sample-02.txt AC 148 ms 12388 KB
00-sample-03.txt AC 149 ms 12388 KB
01-01.txt AC 149 ms 12388 KB
01-02.txt AC 149 ms 12388 KB
01-03.txt AC 148 ms 12388 KB
01-04.txt AC 150 ms 12388 KB
01-05.txt AC 148 ms 12388 KB
01-06.txt AC 149 ms 12388 KB
01-07.txt AC 152 ms 12480 KB
01-08.txt AC 173 ms 16116 KB
01-09.txt AC 179 ms 17456 KB
01-10.txt AC 150 ms 12500 KB
01-11.txt AC 155 ms 12628 KB
01-12.txt AC 186 ms 17560 KB
01-13.txt AC 173 ms 15892 KB
01-14.txt AC 162 ms 14556 KB
01-15.txt AC 163 ms 14884 KB
01-16.txt AC 177 ms 17680 KB
01-17.txt AC 156 ms 13568 KB
01-18.txt AC 155 ms 13140 KB
01-19.txt AC 182 ms 18456 KB
01-20.txt AC 176 ms 16340 KB
01-21.txt AC 187 ms 18448 KB
01-22.txt AC 183 ms 18448 KB
01-23.txt AC 182 ms 18540 KB
01-24.txt AC 183 ms 18448 KB
01-25.txt AC 182 ms 18448 KB
01-26.txt AC 184 ms 18448 KB
01-27.txt AC 187 ms 18448 KB
01-28.txt AC 182 ms 18448 KB
01-29.txt AC 182 ms 18540 KB
01-30.txt AC 181 ms 18448 KB
01-31.txt AC 178 ms 14760 KB
01-32.txt AC 181 ms 17560 KB
01-33.txt AC 180 ms 17944 KB
01-34.txt AC 184 ms 18228 KB
01-35.txt AC 186 ms 18292 KB
01-36.txt AC 179 ms 17432 KB
01-37.txt AC 183 ms 18448 KB
01-38.txt AC 184 ms 18448 KB
01-39.txt AC 181 ms 18448 KB
01-40.txt AC 181 ms 18448 KB
01-41.txt AC 182 ms 18448 KB
01-42.txt AC 182 ms 18448 KB
01-43.txt AC 179 ms 18540 KB
01-44.txt AC 184 ms 18448 KB
01-45.txt AC 183 ms 18448 KB
01-46.txt AC 180 ms 18540 KB
01-47.txt AC 182 ms 18448 KB
01-48.txt AC 181 ms 18448 KB
01-49.txt AC 179 ms 18540 KB
01-50.txt AC 180 ms 18448 KB
01-51.txt AC 180 ms 18540 KB
01-52.txt AC 178 ms 16604 KB
01-53.txt AC 183 ms 15968 KB
01-54.txt AC 184 ms 18448 KB
01-55.txt AC 176 ms 18448 KB
01-56.txt AC 183 ms 18448 KB
01-57.txt AC 176 ms 18448 KB