Problem p02824 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


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

    A.sort()

    # 二分探索で探す
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2

        if N-P <= mid:
            right = mid
            continue

        if A[mid]+M < A[N-P]:
            left = mid
            continue

        # 入れられても構わない票をカウントする
        tot = 0
        for i in range(mid+1, N-P+1):
            tot += A[mid]+M-A[i]
        tot += (P-1)*M
        tot += mid*M
        tot += M

        if tot < M*V:
            left = mid
            continue
        else:
            right = mid
            continue

    print(N-bisect_left(A, A[right]))
    # Yがわかったときの答え

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    A = A[:-(P-1)]
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        C = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        # C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < C[0]:
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # M回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(N-bisect_left(A, Y))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    A = A[:-(P-1)]
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        C = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        # C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(N-bisect_left(A, Y))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(N-bisect_left(A, Y))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from bisect import bisect_left
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            # count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, V-P)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    A.sort()
    # print(A)

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    # print(*A, sep=" ")

    # あるスコアYの問題は最初のP問に入れますか？

    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        # inner_right = 3*(10**9)
        inner_right = 10
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, V-P)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    A.sort()

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    # print(*A, sep=" ")

    # あるスコアYの問題は最初のP問に入れますか？

    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]
        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[0]
        inner_right = 10**9
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(
            # inner_left, inner_right, inner_mid))

            if sum(c < inner_mid for c in C) < V-P:
                # print("A")
                inner_flag = False
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, V-P)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


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

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    A.sort()
    # print(*A, sep=" ")

    # あるスコアYの問題は最初のP問に入れますか？

    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]
        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[0]
        inner_right = 10
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(
            # inner_left, inner_right, inner_mid))

            if sum(c < inner_mid for c in C) < V-P:
                # print("A")
                inner_flag = False
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, V-P)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


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