Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import random
import time

start = time.time()
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]


def main():
    best_score = 0
    best_ans = [0] * 26
    base = list(range(26))
    while time.time() - start < 1.8:
        random.shuffle(base)
        score = calc_score(base)
        if score > best_score:
            best_score = score
            ans = base[:]

    print(*ans, sep='\n')


def calc_score(T):
    score = 0
    last_day = [-1] * 26
    for d, t in enumerate(T):
        score += S[d][t]
        last_day[t] = d
        for c, ld in zip(C, last_day):
            score -= c * (d - ld)
    return score


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    D = int(input())
    C = list(map(int, input().split()))
    S = [list(map(int, input().split())) for _ in range(D)]

    score = 0
    last_day = [-1] * 26

    for d in range(D):
        print(S[d].index(max(S[d])) + 1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
S = input()
N = len(S)
MOD = 10 ** 9 + 7


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, K + N + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)


Fixed submission:
K = int(input())
S = input()
N = len(S)
MOD = 10 ** 9 + 7


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, K + N + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if X[a] == 1])
print(ans)


Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(1000, K)):
    A = calc_imos(A)
print(*A, sep=' ')


Fixed submission:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))


def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    imos = list(accumulate(imos))
    return imos[:-1]


for k in range(min(50, K)):
    A = calc_imos(A)
print(*A, sep=' ')
Buggy python submission (verdict: Runtime Error):
N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

A, B, C = min(A, 2), min(B, 2), min(C, 2)
X = [0, A, B, C]  # 1-indexecの方が楽そう
F = {1: 'A', 2: 'B', 3: 'C'}

ans = []
for k, s in enumerate(S):
    if s == 'AB':
        i, j = 1, 2
    elif s == 'BC':
        i, j = 2, 3
    elif s == 'AC':
        i, j = 1, 3

    if X[i] > X[j]:
        X[i] -= 1
        X[j] += 1
        ans.append(j)

    elif X[i] < X[j]:
        X[i] += 1
        X[j] -= 1
        ans.append(i)

    else:
        if (X[i] == X[j] == 1) and (k < N):
            if ((S[k + 1][0] == F[i]) and (S[k + 1][1] == F[i ^ j])) or ((S[k + 1][0] == F[i ^ j]) and (S[k + 1][1] == F[i])):
                X[i] += 1
                X[j] -= 1
                ans.append(i)
            else:
                X[j] += 1
                X[i] -= 1
                ans.append(j)
        else:
            X[i] -= 1
            X[j] += 1
            ans.append(j)

    if any([x < 0 for x in X]):
        print('No')
        exit()

print('Yes')
for a in ans:
    print(F[a])


Fixed submission:
N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

A, B, C = min(A, 2), min(B, 2), min(C, 2)
X = [0, A, B, C]  # 1-indexecの方が楽そう
F = {1: 'A', 2: 'B', 3: 'C'}

ans = []
for k, s in enumerate(S):
    if s == 'AB':
        i, j = 1, 2
    elif s == 'BC':
        i, j = 2, 3
    elif s == 'AC':
        i, j = 1, 3

    if X[i] > X[j]:
        X[i] -= 1
        X[j] += 1
        ans.append(j)

    elif X[i] < X[j]:
        X[i] += 1
        X[j] -= 1
        ans.append(i)

    else:
        if (X[i] == X[j] == 1) and (k < N - 1):
            if ((S[k + 1][0] == F[i]) and (S[k + 1][1] == F[i ^ j])) or ((S[k + 1][0] == F[i ^ j]) and (S[k + 1][1] == F[i])):
                X[i] += 1
                X[j] -= 1
                ans.append(i)
            else:
                X[j] += 1
                X[i] -= 1
                ans.append(j)
        else:
            X[i] -= 1
            X[j] += 1
            ans.append(j)

    if any([x < 0 for x in X]):
        print('No')
        exit()

print('Yes')
for a in ans:
    print(F[a])
Buggy python submission (verdict: Runtime Error):
A, B, N = map(int, input().split())

def calc(x):
    return ((A * x) // B) - A * (x // B)

prit(max(calc(N), calc(B - 1)))


Fixed submission:
A, B, N = map(int, input().split())


def calc(x):
    return ((A * x) // B) - A * (x // B)


if B == 1:
    print(0)
elif B > N:
    print(calc(N))
else:
    print(calc(B - 1))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
 
D = defaultdict(int)
for a in A:
    D[a] += 1
 
ans_base = 0
for v in D.values():
    ans_base += v * (v - 1) // 2
 
for a in A:
    print(ans_base - (D[a] * (D[a] - 1) // 2) + ((D[a] - 1) * (D[a] - 2) // 2))

Fixed submission:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

D = defaultdict(int)
for a in A:
    D[a] += 1

ans_base = 0
for v in D.values():
    ans_base += v * (v - 1) // 2

for a in A:
    if D[a] > 1:
        print(ans_base - (D[a] * (D[a] - 1) // 2) + ((D[a] - 1) * (D[a] - 2) // 2))
    else:
        print(ans_base)
Buggy python submission (verdict: Time Limit Exceeded):
from decimal import Decimal, getcontext

getcontext().prec = 100000

a, b, c = map(Decimal, input().split())
print('Yes' if a.sqrt() + b.sqrt() < c.sqrt() else 'No')

Fixed submission:
from decimal import *
a, b, c = map(int, input().split())
a, b, c = Decimal(a).sqrt(), Decimal(b).sqrt(), Decimal(c).sqrt()

if a + b < c:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = list(map(int, list(str(N))))


dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))


Fixed submission:
N = input()
X = list(map(int, list(str(N))))

dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = list(map(int, list(str(N))))


dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))


Fixed submission:
N = input()
X = list(map(int, list(str(N))))

dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))
Buggy python submission (verdict: Runtime Error):
def main():
    from math import ceil
    from bisect import bisect_right
    N, D, A = map(int, input().split())
    Monsters = [list(map(int, input().split())) for i in range(N)]
    Monsters = sorted([[x, ceil(h / A)] for x, h in Monsters])


    class BIT2:
        """ 区間加算BIT(区間加算・区間合計取得) """

        def __init__(self, N):
            self.N = N
            self.data0 = [0] * N
            self.data1 = [0] * N

        def _add(self, data, k, x):
            while k < self.N:
                data[k] += x
                k += k & -k

        def _get(self, data, k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s

        def add(self, l, r, x):
            """ 区間[l,r)に値xを追加 """

            self._add(self.data0, l, -x*(l-1))
            self._add(self.data0, r, x*(r-1))
            self._add(self.data1, l, x)
            self._add(self.data1, r, -x)

        def query(self, l, r):
            """ 区間[l,r)の和を取得 """

            return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
                 - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)


    RUQ = BIT2(2 * N)
    for i, (x, h) in enumerate(Monsters, start=1):
        RUQ.add(i, i + 1, h)


    i = 0
    ans = 0
    while i < N:
        cost = RUQ.query(i + 1, i + 2)
        if cost > 0:
            index = bisect_right(Monsters, [Monsters[i][0] + 2 * D, float('inf')])
            RUQ.add(i + 1, index + 1, -cost)
            ans += cost
        i += 1
        #
        # check = []
        # for j in range(1, N + 1):
        #     check.append(str(RUQ.query(j, j + 1)))
        # print(' '.join(check))

    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
from math import ceil
H, A = map(int, input().split())
print(ceil(H / A))
Buggy python submission (verdict: Runtime Error):
from math import ceil
N, M = map(int, input().split())
A = list(map(int, input().split()))
m = min(A)
A = [a // 2 for a in A]


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)


while len(A) > 1:
    A.append(lcm(A.pop(), A.pop()))

X = A[0]
print(ceil((M // X) / 2) - int(X / m < 1))


Fixed submission:
from math import ceil
N, M = map(int, input().split())
A = list(map(int, input().split()))


# 2で割ったものに置き換え
A = [a // 2 for a in A]


# 各要素について、2で割り切れる回数が等しいかチェック
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1

    if count_div_2 is None:
        count_div_2 = cnt
    elif cnt != count_div_2:
        print(0)
        exit()


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a // gcd(a, b) * b


while len(A) > 1:
    a, b = A.pop(), A.pop()
    my_lcm = lcm(a, b)

    # Mを超えたlcmは意味がない
    if my_lcm > M:
        print(0)
        exit()

    A.append(my_lcm)


print(ceil(M // A[0] / 2))
Buggy python submission (verdict: Runtime Error):
H, W, K = map(int, input().split())
S = [list(input()) for i in range(H)]

non_placed_h = set()
for h in range(H):
    if S[h].count('#') == 0:
        non_placed_h.add(h)

ans = [[0] * W for i in range(H)]
x = 0

for h in range(H):
    if h in non_placed_h:
        continue

    else:
        x_cnt = 0
        x += 1

        for w in range(W):
            if S[h][w] == '#':
                x_cnt += 1
                if x_cnt >= 2:
                    x += 1
            ans[h][w] = x

for h in range(H - 1, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

for h in range(H - 1, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

m = float('inf')
for a in ans:
    m = min(m, min(a))

d = m - 1

for i in range(H):
    for j in range(W):
        ans[i][j] -= d

for a in ans:
    print(' '.join(map(str, a)))



Fixed submission:
H, W, K = map(int, input().split())
S = [list(input()) for i in range(H)]

non_placed_h = set()
for h in range(H):
    if S[h].count('#') == 0:
        non_placed_h.add(h)

ans = [[0] * W for i in range(H)]
x = 0

for h in range(H):
    if h in non_placed_h:
        continue

    else:
        x_cnt = 0
        x += 1

        for w in range(W):
            if S[h][w] == '#':
                x_cnt += 1
                if x_cnt >= 2:
                    x += 1
            ans[h][w] = x

for h in range(H - 2, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

for h in range(H - 2, -1, -1):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h + 1][w]

for h in range(1, H):
    for w in range(W):
        if ans[h][w] == 0:
            ans[h][w] = ans[h - 1][w]

m = float('inf')
for a in ans:
    m = min(m, min(a))

d = m - 1

for i in range(H):
    for j in range(W):
        ans[i][j] -= d

for a in ans:
    print(' '.join(map(str, a)))
Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())
MOD = 10 ** 9 + 7


if (X + Y) % 3 != 0:
    print(0)
    exit()


X, Y = min(X, Y), max(X, Y)
ALL_MOVE = (X + Y) // 3

for m1 in range(ALL_MOVE):
    m2 = ALL_MOVE - m1

    if (m1 * 2 + m2 == X) and (m1 + m2 * 2 == Y):
        move_1_cnt = m1
        move_2_cnt = m2
        break


factorial = [1]
inverse = [1]
for i in range(1, ALL_MOVE + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


print(nCr(ALL_MOVE, move_1_cnt) % MOD)


Fixed submission:
X, Y = map(int, input().split())
MOD = 10 ** 9 + 7


if (X + Y) % 3 != 0:
    print(0)
    exit()


X, Y = min(X, Y), max(X, Y)
ALL_MOVE = (X + Y) // 3
for m1 in range(ALL_MOVE):
    m2 = ALL_MOVE - m1

    if (m1 * 2 + m2 == X) and (m1 + m2 * 2 == Y):
        move_1_cnt = m1
        move_2_cnt = m2
        break
else:
    print(0)
    exit()


factorial = [1]
inverse = [1]
for i in range(1, ALL_MOVE + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


print(nCr(ALL_MOVE, move_1_cnt) % MOD)
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])

# dp1[i][j] := 商品0 ~ i が対象
dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
for i, (wi, vi) in enumerate(items):
    for j in range(W):
        ans = max(ans, dp[i] + vi)

print(ans)


Fixed submission:
N, T = map(int, input().split())
T -= 1
Meals = sorted([list(map(int, input().split())) for i in range(N)])
dp = [[0] * (T + 1) for i in range(N + 1)]
prev = [[-1] * (T + 1) for i in range(N + 1)]


for i, (cost, value) in enumerate(Meals):
    for j in range(T + 1):
        if j >= cost:
            if dp[i + 1][j] <= dp[i][j - cost] + value:
                dp[i + 1][j] = dp[i][j - cost] + value
                prev[i + 1][j] = j - cost

        if dp[i + 1][j] <= dp[i][j]:
            dp[i + 1][j] = dp[i][j]
            prev[i + 1][j] = j

# 復元
selected = set()
cur_w = T
for i in range(N - 1, -1, -1):
    if prev[i + 1][cur_w] == cur_w - Meals[i][0]:
        selected.add(i)
    cur_w = prev[i + 1][cur_w]

non_selected = set(list(range(N))) - selected
ans = dp[N][T]
add = 0
for ni in non_selected:
    add = max(add, Meals[ni][1])

print(dp[N][T] + add)
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
from collections import Counter
N = int(input())
L = sorted(list(map(int, input().split())))


acc = [0] * 1001
for l in L:
    acc[l] += 1
acc = list(accumulate(acc))


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        l1, l2 = L[i], L[j]
        if l1 == l2:
            continue
        ans += acc[min(1000, l1 + l2 - 1)] - acc[l2]

C = Counter(L)
for k, v in C.items():
    if v >= 3:
        ans += v * (v - 1) * (v - 2) // 6

for k, v in C.items():
    if v >= 2:
        ans += v * (v - 1) // 2 * (acc[min(1000, 2 * v - 1)] - acc[v])

print(ans)


Fixed submission:
from bisect import bisect_right
N = int(input())
L = sorted(list(map(int, input().split())))
L = [(l, i) for i, l in enumerate(L)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        l1_value, l1_index = L[i]
        l2_value, l2_index = L[j]
        ans += max(0, (bisect_right(L, (l1_value + l2_value, l2_index))) - j - 1)

print(ans)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

common_divisors = []
for n in range(1, int(max(A, B) ** 0.5) + 1):
    if (A % n == 0) & (B % n == 0):
        common_divisors.append(n)


# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


Primes = eratosthenes(max(A, B) + 1)
Primes_set = set(Primes)

ans = 0
for cd in common_divisors:
    if cd in Primes_set:
        ans += 1

print(ans + 1)


Fixed submission:
A, B = map(int, input().split())

common_divisors = []
for n in range(1, int(min(A, B) ** 0.5) + 1):
    if (A % n == 0) & (B % n == 0):
        common_divisors.append(n)

    if A % n == 0:
        x = A // n
        if B % x == 0:
            common_divisors.append(x)


# ある自然数の素数判定
def is_prime(n):
    if n == 1:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    else:
        return True


ans = 0
for cd in common_divisors:
    ans += is_prime(cd)

print(ans + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
keys = []
for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (c - 1) for c in list(map(int, input().split()))])
    keys.append([a, c])


# dp[bs] := 鍵の集合bsを手に入れるのに必要な最小費用
dp = [float('inf')] * (1 << N)
dp[0] = 0

for i, (cost, key) in enumerate(keys):
    for bs in range(1 << N):
        dp[bs | key] = min(dp[bs | key], dp[bs] + cost)

print(dp[-1] if dp[-1] != float('inf') else -1)


Fixed submission:
N, M = map(int, input().split())
Keys = []
keys_set = set()

for m in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    c = [2 ** (ci - 1) for ci in c]
    Keys.append([a, sum(c)])
    keys_set |= set(c)


# 不可能判定
if len(keys_set) != N:
    print(-1)
    exit()


dp = [[float('inf')] * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i, (a, c) in enumerate(Keys):
    for bs in range(2 ** N):
        dp[i + 1][bs] = min(dp[i + 1][bs], dp[i][bs])
        dp[i + 1][bs | c] = min(dp[i][bs | c], dp[i + 1][bs | c], dp[i][bs] + a)

ans = float('inf')
for d in dp:
    ans = min(ans, d[-1])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

B = [0] * N
for i in reversed(range(N)):
    ball = 0
    base = i + 1

    for j in range(1, N + 1):
        if ball * j - 1 >= N:
            break
        ball += B[ball * j - 1]

    if ball % 2 != A[i]:
        B[i] = 1

print(sum(B))
print(*[i for i, b in enumerate(B, start=1) if b == 1], sep=' ')


Fixed submission:
N = int(input())
A = [0] + list(map(int, input().split()))

B = [0] * (N + 1)

for i in reversed(range(1, N + 1)):
    tmp = 0
    for j in range(i, N + 1, i):
        tmp += B[j]

    if tmp % 2 != A[i]:
        B[i] = 1

for i in range(1, N + 1):
    tmp = 0
    for j in range(i, N + 1, i):
        tmp += B[j]
    if A[i] != tmp % 2:
        print(-1)
        exit()

print(sum(B))
ans = []
for i, b in enumerate(B):
    if b == 1:
        ans.append(i)
if len(ans) > 0:
    print(*ans, sep=' ')