Problem p02616 (python)

Fixed submission:
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1

def min_pos(arr):
    pass


if k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
elif neg_cnt == n and k % 2 == 1:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[v]), reverse=True)
    pos.sort(key=lambda v: abs(arr[v]), reverse=True)


    if k % 2:
        res = arr[pos[0]]
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k and (i < len(pos) - 1 or j < len(neg) - 1):
        if j >= len(neg) - 1 or i < len(pos) - 1 and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    while i + j < k:
        res *= arr[pos[i]]
        i += 1
        res %= modulo

    print(res)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]))
    pos.sort(key=lambda v: abs(arr[i]))

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k:
        if j == len(neg) or i < len(pos) and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    print(res)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def min_pos(arr):
    pass


if neg_cnt == n:
    res = 1
    arr.sort(reverse=True)
    for i in range(k):
        res *= arr[i]
        res %= modulo
    print(res)
elif k == n:
    res = 1
    for v in arr:
        res *= v
        res %= modulo
    print(res)
else:
    pos = []
    neg = []
    for i, v in enumerate(arr):
        if v < 0:
            neg.append(i)
        else:
            pos.append(i)

    neg.sort(key=lambda v: abs(arr[i]))
    pos.sort(key=lambda v: abs(arr[i]))

    if k % 2:
        res = arr[pos[0]] % modulo
        i = 1
    else:
        res = 1
        i = 0
    j = 0
    while i + j < k:
        if j == len(pos) or i < len(pos) and arr[pos[i]] * arr[pos[i + 1]] > arr[neg[j]] * arr[neg[j + 1]]:
            res *= arr[pos[i]]
            res *= arr[pos[i + 1]]
            i += 2
        else:
            res *= arr[neg[j]]
            res *= arr[neg[j + 1]]
            j += 2
        res %= modulo

    print(res)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def max_pos(arr):
    arr.sort(key=lambda obj: abs(obj), reverse=True)

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 0 or k == len(arr):
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) > abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo

def min_pos(arr):
    arr.sort(key=lambda obj: abs(obj))

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 1 or k == len(arr):
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) < abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        print(next_pos)
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo


if neg_cnt == n and k % 2 == 1:
    print(min_pos(arr))
elif k == 1:
    print(max(arr) % modulo)
else:
    print(max_pos(arr))

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
modulo = 10 ** 9 + 7
*arr, = map(int, input().split())
inverses = [pow(v, modulo - 2, modulo) for v in arr]
neg_cnt = 0
for v in arr:
    if v < 0:
        neg_cnt += 1


def max_pos(arr):
    arr.sort(key=lambda obj: abs(obj), reverse=True)

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 0:
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) > abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo

def min_pos(arr):
    arr.sort(key=lambda obj: abs(obj))

    neg = []
    pos = []
    res = 1
    for i in range(k):
        res *= arr[i]
        res %= modulo
        if arr[i] < 0:
            neg.append(i)
        else:
            pos.append(i)

    if len(neg) % 2 == 1:
        return res

    next_neg = i
    next_pos = i
    while next_neg < len(arr) and arr[next_neg] >= 0:
        next_neg += 1

    while next_pos < len(arr) and arr[next_pos] < 0:
        next_pos += 1

    prev_neg = neg[-1]
    prev_pos = -1 if not pos else pos[-1]

    if (prev_pos == -1 or abs(arr[next_pos] * arr[prev_neg]) < abs(arr[prev_pos] * arr[next_neg])) and next_pos != len(arr):
        print(next_pos)
        return (res * arr[next_pos] * inverses[prev_neg]) % modulo
    return (res * arr[next_neg] * inverses[prev_pos]) % modulo


if neg_cnt == n and k % 2 == 1:
    print(min_pos(arr))
elif k == 1:
    print(max(arr) % modulo)
else:
    print(max_pos(arr))