Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
while True:
    n, m, h, k = map(int, input().split())
    if not n:
        break
    points = [int(input()) for _ in range(n)]
    bars = [tuple(map(int, input().split())) for _ in range(m)]
    bars_h = [set() for _ in range(h)]
    for ba, bh in bars:
        bars_h[bh].add(ba - 1)
    swap = [points] + [None] * m
    pattern = 1

    for i in range(h - 1, 0, -1):
        for ba in bars_h[i]:
            swap[pattern] = swap[0][:]
            for s in swap[:pattern]:
                s[ba], s[ba + 1] = s[ba + 1], s[ba]
            pattern += 1

    print(min(sum(s[:k]) for s in swap))

Fixed submission:
while True:
    n, m, h, k = map(int, input().split())
    if not n:
        break
    points = [int(input()) for _ in range(n)]
    bars = [tuple(map(int, input().split())) for _ in range(m)]
    bars_h = [set() for _ in range(h)]
    for ba, bh in bars:
        bars_h[bh].add(ba - 1)
    swap = list(range(n))
    history = set()

    for i in range(h - 1, 0, -1):
        for ba in bars_h[i]:
            l, r = swap[ba:ba + 2]
            history.add((l, r) if l < r else (r, l))
            swap[ba:ba + 2] = r, l
    swap_dict = {v: i for i, v in enumerate(swap)}
    min_score_d = 0
    for l, r in history:
        li, ri = swap_dict[l], swap_dict[r]
        if li > ri:
            l, r, li, ri = r, l, ri, li
        if li < k and k <= ri:
            min_score_d = min(min_score_d, points[r] - points[l])

    print(sum(points[x] for x in swap[:k]) + min_score_d)
Buggy python submission (verdict: Runtime Error):
from collections import deque
from itertools import chain, combinations

n, k = map(int, input().split())
books = [[] for _ in range(10)]

while n:
    c, g = map(int, input().split())
    books[g - 1].append(c)
    n -= 1

for q in books:
    q.sort(reverse=True)

done = set()
max_cost = 0

for book_combi in combinations(chain.from_iterable([[i] * min(k, len(q)) for i, q in enumerate(books) if q]), k):
    if book_combi in done:
        continue
    done.add(book_combi)

    cost = 0
    counts = [0] * 10
    for i in book_combi:
        cost += books[i][counts[i]] + counts[i] * 2
        counts[i] += 1

    if cost > max_cost:
        max_cost = cost

print(max_cost)

Fixed submission:
from itertools import accumulate

n, k = map(int, input().split())
books = [[] for _ in range(10)]

while n:
    c, g = map(int, input().split())
    books[g - 1].append(c)
    n -= 1

books_acc = [[0] + list(accumulate(c + i * 2 for i, c in enumerate(sorted(q, reverse=True)))) for q in books]


def memoize(f):
    memo = [[-1] * (k + 1) for _ in range(10)]

    def main(x, y):
        if x > 9:
            return 0
        result = memo[x][y]
        if result < 0:
            result = memo[x][y] = f(x, y)
        return result

    return main


@memoize
def combi(g, remain):
    book_acc = list(books_acc[g])
    salable = min(remain + 1, len(book_acc))
    return max([book_acc[i] + combi(g + 1, remain - i) for i in range(salable)], default=0)


print(combi(0, k))
Buggy python submission (verdict: Time Limit Exceeded):
import fileinput

for line in fileinput.input():
    n = int(line)
    sqn = n ** 0.5
    ps = set()
    for i in range(3, n + 1, 2):
        for p in ps:
            if p > sqn:
                continue
            if i % p == 0:
                break
        else:
            ps.add(i)
        i += 2
    ps.add(2)

    print(sum(i in ps and (n + 1 - i) in ps for i in range(2, n + 1)))

Fixed submission:
import fileinput

ps = set()
for i in range(3, 10001, 2):
    for p in ps:
        if p > 100:
            continue
        if i % p == 0:
            break
    else:
        ps.add(i)
    i += 2
ps.add(2)

for line in fileinput.input():
    n = int(line)
    print(sum(i in ps and (n + 1 - i) in ps for i in range(2, n + 1)))
Buggy python submission (verdict: Runtime Error):
while True:
    n = int(input())
    if not n:
        break
    a = [list(map(int, input().split())) for j in range(n)]
    c = [max(a[i][j] for i in range(n)) for j in range(n)]
    r = [min(a[i]) for i in range(n)]

    print([c[j] for i in range(n) for j, x in enumerate(a[i]) if x == r[i] and c[j] == r[i]][0])

Fixed submission:
while True:
    n = int(input())
    if not n: break
    a = [list(map(int, input().split())) for _ in range(n)]
    s = max(min(a[i]) for i in range(n))
    c = [max(a[i][j] for i in range(n)) for j in range(n)]
    for j in range(n):
        if c[j] == s:
            print(s)
            break
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
while True:
    n = int(input())
    if not n:
        break
    stars = list(map(int, input().split()))
    half_n = n // 2
    for s in set(stars):
        if stars.count(s) > half_n:
            print(s)
            break
    else:
        print('NO COLOR')

Fixed submission:
from collections import defaultdict

while True:
    n = int(input())
    if not n:
        break
    stars = defaultdict(int)
    for s in map(int, input().split()):
        stars[s] += 1
    half_n = n // 2
    for i, s in stars.items():
        if s > half_n:
            print(i)
            break
    else:
        print('NO COLOR')
Buggy python submission (verdict: Runtime Error):
from math import gcd

while True:
    a, b, c = map(int, input().split())
    if not a:
        break
    d = (b ** 2 - 4 * a * c) ** 0.5
    if isinstance(d, complex) or d - int(d) > 1e-6:
        print('Impossible')
        continue
    num1, num2 = -b + int(d), -b - int(d)
    den = 2 * a
    cmn1, cmn2 = gcd(num1, den), gcd(num2, den)
    print(den // cmn1, -num1 // cmn1, den // cmn2, -num2 // cmn2)

Fixed submission:
import fractions

while True:
    a, b, c = map(int, input().split())
    if not a:
        break
    d = (b ** 2 - 4 * a * c) ** 0.5
    if isinstance(d, complex) or d - int(d) > 1e-6:
        print('Impossible')
        continue
    num1, num2 = -b + int(d), -b - int(d)
    den = 2 * a
    cmn1, cmn2 = fractions.gcd(num1, den), fractions.gcd(num2, den)
    p, q, r, s = den // cmn1, -num1 // cmn1, den // cmn2, -num2 // cmn2
    if (p, q) < (r, s):
        p, q, r, s = r, s, p, q
    print(p, q, r, s)
Buggy python submission (verdict: Runtime Error):
from heapq import heapify, heappop, heappush
from operator import add

while True:
    n, m, s, g1, g2 = map(int, input().split())
    s -= 1
    g1 -= 1
    g2 -= 1
    if not n:
        break
    pipes = [set() for _ in range(n)]
    for _ in range(m):
        b1, b2, c = map(int, input().split())
        b1 -= 1
        b2 -= 1
        pipes[b1].add((c, b2))
        pipes[b2].add((c, b1))

    dists = [[None] * n for _ in range(2)]

    for i in (0, 1):
        g = (g1, g2)[i]
        dist = dists[i]
        dist[g] = 0
        queue = list(pipes[g])
        heapify(queue)
        while queue:
            total_cost, base = heappop(queue)
            if dist[base] is not None:
                continue
            dist[base] = total_cost
            for next_cost, next_base in pipes[base]:
                if dist[next_base] is None:
                    heappush(queue, (total_cost + next_cost, next_base))

    dists = list(map(add, *dists))

    current_best = dists[s]
    queue = list(pipes[s])
    heapify(queue)
    visited = {s}
    while queue:
        total_cost, base = heappop(queue)
        if base in visited:
            continue
        visited.add(base)
        current_best = min(current_best, total_cost + dists[base])
        for next_cost, next_base in pipes[base]:
            if next_base not in visited:
                next_whole_cost = total_cost + next_cost + dists[next_base]
                if current_best > next_whole_cost:
                    heappush(queue, (total_cost + next_cost, next_base))

    print(current_best)

Fixed submission:
from heapq import heapify, heappop, heappush
from operator import add

SENTINEL = 100000
while True:
    n, m, s, g1, g2 = map(int, input().split())
    s -= 1
    g1 -= 1
    g2 -= 1
    if not n:
        break
    pipes = [set() for _ in range(n)]
    rpipes = [set() for _ in range(n)]
    for _ in range(m):
        b1, b2, c = map(int, input().split())
        b1 -= 1
        b2 -= 1
        pipes[b1].add((c, b2))
        rpipes[b2].add((c, b1))

    dists = [[SENTINEL] * n for _ in range(2)]

    for i in (0, 1):
        g = (g1, g2)[i]
        dist = dists[i]
        dist[g] = 0
        queue = list(rpipes[g])
        heapify(queue)
        while queue:
            total_cost, base = heappop(queue)
            if dist[base] < SENTINEL:
                continue
            dist[base] = total_cost
            for next_cost, next_base in rpipes[base]:
                if dist[next_base] == SENTINEL:
                    heappush(queue, (total_cost + next_cost, next_base))

    dists = list(map(add, *dists))

    current_best = dists[s]
    queue = list(pipes[s])
    heapify(queue)
    visited = {s}
    while queue:
        total_cost, base = heappop(queue)
        if base in visited:
            continue
        visited.add(base)
        current_best = min(current_best, total_cost + dists[base])
        for next_cost, next_base in pipes[base]:
            if next_base not in visited:
                heappush(queue, (total_cost + next_cost, next_base))

    print(current_best)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from itertools import accumulate

buf = []
while True:
    n, m = int(input())
    if n == 0:
        break
    hs = [int(input()) for _ in range(n)]
    ws = [int(input()) for _ in range(m)]
    ha = accumulate(hs)
    wa = accumulate(ws)
    hd = defaultdict(int)
    wd = defaultdict(int)

    for i in range(n):
        for j in range(i + 1, n):
            hd[ha[j] - ha[i]] += 1
            wd[wa[j] - wa[i]] += 1
    ans = 0
    for h, cnt in hd.items():
        if h in wd:
            ans += cnt * wd[h]
    buf.append(ans)

print('\n'.join(map(str, buf)))

Fixed submission:
from collections import defaultdict
from itertools import accumulate

buf = []
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    hs = [int(input()) for _ in range(n)]
    ws = [int(input()) for _ in range(m)]
    ha = [0] + list(accumulate(hs))
    wa = [0] + list(accumulate(ws))
    hd = defaultdict(int)
    wd = defaultdict(int)

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            hd[ha[j] - ha[i]] += 1
    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            wd[wa[j] - wa[i]] += 1
    ans = 0
    for h, cnt in hd.items():
        if h in wd:
            ans += cnt * wd[h]
    buf.append(ans)

print('\n'.join(map(str, buf)))
Buggy python submission (verdict: Runtime Error):
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    risks = [(p, d) for d, p in (map(int, input().split()) for _ in range(n))]
    risks.sort()
    while m:
        p, d = risks.pop()
        if d >= m:
            remain = p * (d - m)
            break
        m -= d
    print(remain + sum(p * d for p, d in risks))

Fixed submission:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    risks = [(p, d) for d, p in (map(int, input().split()) for _ in range(n))]
    risks.sort()
    remain = 0
    while risks:
        p, d = risks.pop()
        if d >= m:
            remain = p * (d - m)
            break
        m -= d
    print(remain + sum(p * d for p, d in risks))

Buggy python submission (verdict: Runtime Error):
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    risks = [(p, d) for d, p in (map(int, input().split()) for _ in range(n))]
    risks.sort()
    remain = 0
    while m:
        p, d = risks.pop()
        if d >= m:
            remain = p * (d - m)
            break
        m -= d
    print(remain + sum(p * d for p, d in risks))

Fixed submission:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    risks = [(p, d) for d, p in (map(int, input().split()) for _ in range(n))]
    risks.sort()
    remain = 0
    while risks:
        p, d = risks.pop()
        if d >= m:
            remain = p * (d - m)
            break
        m -= d
    print(remain + sum(p * d for p, d in risks))
Buggy python submission (verdict: Time Limit Exceeded):
t, p = input(), input()
start, len_p = 0, len(p)
while True:
    idx = t.find(p, start)
    if idx == -1:
        break
    print(idx)
    start = idx + 1

Fixed submission:
def make_kmp_table(t):
    i = 2
    j = 0
    m = len(t)
    tbl = [0] * (m + 1)
    tbl[0] = -1
    while i <= m:
        if t[i - 1] == t[j]:
            tbl[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = tbl[j]
        else:
            tbl[i] = 0
            i += 1
    return tbl


def kmp(s, t):
    matched_indices = []
    tbl = make_kmp_table(t)
    i = 0
    j = 0
    n = len(s)
    m = len(t)
    while i + j < n:
        if t[j] == s[i + j]:
            j += 1
            if j == m:
                matched_indices.append(i)
                i += j - tbl[j]
                j = tbl[j]
        else:
            i += j - tbl[j]
            if j > 0:
                j = tbl[j]
    return matched_indices


t = input()
p = input()
result = kmp(t, p)
if result:
    print(*result, sep='\n')
Buggy python submission (verdict: Runtime Error):
from functools import reduce
from collections import deque


def operate(dq, op):
    if op[0] == 'i':
        dq.appendleft(int(op[7:]))
    else:
        k = op[6]
        if k == 'F':
            dq.popleft()
        elif k == 'L':
            dq.pop()
        else:
            dq.remove(int(op[7:]))
    return dq


n = int(input())
print(*reduce(operate, [input() for _ in range(n)], deque()))

Fixed submission:
from functools import reduce
from collections import deque


def operate(dq, op):
    if op[0] == 'i':
        dq.appendleft(int(op[7:]))
    else:
        k = op[6]
        if k == 'F':
            dq.popleft()
        elif k == 'L':
            dq.pop()
        else:
            try:
                dq.remove(int(op[7:]))
            except ValueError:
                pass
    return dq


n = int(input())
print(*reduce(operate, [input() for _ in range(n)], deque()))
Buggy python submission (verdict: Runtime Error):
from collections import deque


def marge_ponds(lx, area_of_pond):
    global ponds
    if ponds and ponds[-1][0] > lx:
        return marge_ponds(lx, area_of_pond + ponds.pop()[1])
    return area_of_pond


terrains = input().strip()
x, last_x, ponds = 0, deque(), deque()

for terrain in terrains:
    if terrain == '\\':
        last_x.append(x)
    elif terrain == '/':
        if last_x:
            lx = last_x.pop()
            ponds.append((lx, marge_ponds(lx, x - lx)))
    x += 1

print(sum(pond[1] for pond in ponds))
ponds.insert(0, (0, len(ponds)))
print(' '.join(map(str, [pond[1] for pond in ponds])))

Fixed submission:
from collections import deque


def marge_ponds(lx, area_of_pond):
    global ponds
    if ponds and ponds[-1][0] > lx:
        return marge_ponds(lx, area_of_pond + ponds.pop()[1])
    return area_of_pond


terrains = input().strip()
x, last_x, ponds = 0, deque(), deque()

for terrain in terrains:
    if terrain == '\\':
        last_x.append(x)
    elif terrain == '/':
        if last_x:
            lx = last_x.pop()
            ponds.append((lx, marge_ponds(lx, x - lx)))
    x += 1

print(sum(pond[1] for pond in ponds))
ponds.appendleft((0, len(ponds)))
print(' '.join(map(str, [pond[1] for pond in ponds])))
Buggy python submission (verdict: Runtime Error):
n, s, q, t = int(input()), list(set(map(int, input().split()))), input(), set(map(int, input().split()))


# print(sum(i in s for i in t))

def binary_search(i):
    global n, s
    l, r = 0, n
    while l < r:
        m = (l + r) // 2
        sm = s[m]
        if sm == i:
            return 1
        elif i < sm:
            r = m
        else:
            l = m + 1
    return 0


print(sum(binary_search(i) for i in t))

Fixed submission:
n, s, q, t = input(), list(set(map(int, input().split()))), input(), set(map(int, input().split()))

# print(sum(i in s for i in t))
s.sort()


def binary_search(i):
    global s
    l, r = 0, len(s)
    while l < r:
        m = (l + r) // 2
        sm = s[m]
        if sm == i:
            return 1
        elif i < sm:
            r = m
        else:
            l = m + 1
    return 0


print(sum(binary_search(i) for i in t))
Buggy python submission (verdict: Time Limit Exceeded):
l, n = [], int(input().strip())

for _ in range(n):
    opr, word = input().strip().split()
    word = int(word.translate(str.maketrans('ACGT', '1234')), base=5)
    if opr.startswith('i'):
        l.append(word)
    else:
        print('yes' if word in l else 'no')

Fixed submission:
l, n, r = set(), int(input()), str.maketrans('ACGT', '1234')

for _ in range(n):
    opr, word = input().split()
    word = int(word.translate(r), base=5)
    if opr.startswith('i'):
        l.add(word)
    else:
        print('yes' if word in l else 'no')
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil


def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


n, k = map(int, input().split())

ws = [int(input()) for _ in range(n)]

p = max(ceil(sum(ws) / k), *ws)

while True:
    if check_p(p):
        break
    p += 1

print(p)

Fixed submission:
def check_p(p):
    global k, ws
    lt, nt = 0, 1  # loadage_of_current_truck, num_of_truck
    for w in ws:
        lt += w
        if lt > p:
            nt += 1
            if nt > k:
                return False
            lt = w
    return True


n, k = map(int, input().split())

ws = [int(input()) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)
Buggy python submission (verdict: Time Limit Exceeded):
n, a, q, ms = int(input()), list(map(int, input().split())), input(), map(int, input().split())


def check(m, bin):
    global a
    s = 0
    for b in a:
        if bin & 1:
            s += b
            if s > m:
                return False
        bin >>= 1
    return s == m


for m in ms:
    for i in range(1, 2 ** n - 1):
        if check(m, i):
            print('yes')
            break
    else:
        print('no')

Fixed submission:
from itertools import combinations

n, a, q = int(input()), list(map(int, input().split())), input()

l = set(sum(t) for i in range(n) for t in combinations(a, i + 1))

for m in map(int, input().split()):
    print('yes' if m in l else 'no')

Buggy python submission (verdict: Time Limit Exceeded):
n, a, q, ms = int(input()), list(map(int, input().split())), input(), map(int, input().split())

cache = {}


def sum_a(tmp, b, i=0, mask=1):
    global a, cache
    if not b:
        return tmp
    elif b in cache:
        return tmp + cache[b]
    elif b & mask:
        tmp += a[i]
        new_b = b ^ mask
    else:
        new_b = b
    result = sum_a(tmp, new_b, i + 1, mask << 1)
    cache[b] = result
    return result


for m in ms:
    for b in range(1, 2 ** n):
        if sum_a(0, b) == m:
            print('yes')
            break
    else:
        print('no')

Fixed submission:
from itertools import combinations

n, a, q = int(input()), list(map(int, input().split())), input()

l = set(sum(t) for i in range(n) for t in combinations(a, i + 1))

for m in map(int, input().split()):
    print('yes' if m in l else 'no')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def merge(a, l, m, r):
    global cnt
    n1, n2 = m - l, r - m
    ll = deque(a[l + i] for i in range(n1))
    rl = deque(a[m + i] for i in range(n2))
    for k in range(l, r):
        a[k] = (ll if not rl or ll and ll[0] <= rl[0] else rl).popleft()
        cnt += 1


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(*a)
print(cnt)

Fixed submission:
from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    ll.append(INFTY)
    rl.append(INFTY)
    for k in range(l, r):
        a[k] = (ll if ll[0] < rl[0] else rl).popleft()
    cnt += r - l


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(*a)
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
def merge(a, l, m, r):
    global cnt
    n1, n2 = m - l, r - m
    ll = list(a[l + i] for i in range(n1))
    rl = list(a[m + i] for i in range(n2))
    ll.append(1e9 + 1)
    rl.append(1e9 + 1)
    i, j = 0, 0
    for k in range(l, r):
        if ll[i] < rl[j]:
            a[k] = ll[i]
            i += 1
        else:
            a[k] = rl[j]
            j += 1
        cnt += 1


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(*a)
print(cnt)

Fixed submission:
from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    ll.append(INFTY)
    rl.append(INFTY)
    for k in range(l, r):
        a[k] = (ll if ll[0] < rl[0] else rl).popleft()
    cnt += r - l


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(*a)
print(cnt)
Buggy python submission (verdict: Runtime Error):
class Bit:
    def __init__(self, size):
        self.arr = [0] * (size + 1)
        self.size = size

    def read(self, index):
        sum_b = 0
        while index:
            sum_b += self.arr[index]
            index &= index - 1
        return sum_b

    def update(self, index, value=1):
        while index <= self.size:
            self.arr[index] += value
            index += index & -index


bit, a, inv = Bit(int(input())), list(map(int, input().split())), 0

for i in reversed(a):
    inv += bit.read(i)
    bit.update(i)
print(inv)

Fixed submission:
from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    for k in range(l, r):
        if not rl or ll and ll[0] < rl[0]:
            a[k] = ll.popleft()
        else:
            a[k] = rl.popleft()
            cnt += len(ll)


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


n, a, cnt = int(input()), list(map(int, input().split())), 0
merge_sort(a, 0, n)
print(cnt)