Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys

N, T = map(int, input().split())
S = sys.stdin.readlines()
A = []
B = []
for s in S:
    a, b = map(int, s.split())
    A.append(a)
    B.append(b)

dp1 = [[0] * T for _ in range(N + 1)]
for i in range(N):
    for j in range(T):
        here = dp1[i][j]
        if j < A[i]:
            dp1[i + 1][j] = here
        else:
            dp1[i + 1][j] = max(here, dp1[i][j - A[i]] + B[i])

dp2 = [[0] * T for _ in range(N + 2)]
for i in range(N, 0, -1):
    for j in range(T):
        here = dp2[i + 1][j]
        if j < A[i - 1]:
            dp2[i][j] = here
        else:
            dp2[i][j] = max(here, dp2[i + 1][j - A[i - 1]] + B[i - 1])

ans = 0
for i in range(1, N + 1):
    t = 0
    for j in range(T):
        t2 = dp1[i - 1][j] + dp2[i + 1][T - 1 - j]
        t = max(t, t2)
    ans = max(ans, t + B[i - 1])

print(ans)


Fixed submission:
import sys

N, T = map(int, input().split())
S = sys.stdin.readlines()
A = []
B = []
for s in S:
    a, b = map(int, s.split())
    A.append(a)
    B.append(b)

dp1 = [[0] * T for _ in range(N + 1)]
for i in range(N):
    for j in range(T):
        here = dp1[i][j]
        if j < A[i]:
            dp1[i + 1][j] = here
        else:
            dp1[i + 1][j] = max(here, dp1[i][j - A[i]] + B[i])

dp2 = [[0] * T for _ in range(N + 2)]
for i in range(N, 0, -1):
    for j in range(T):
        here = dp2[i + 1][j]
        if j < A[i - 1]:
            dp2[i][j] = here
        else:
            dp2[i][j] = max(here, dp2[i + 1][j - A[i - 1]] + B[i - 1])

ans = 0
for i in range(1, N + 1):
    t = 0
    for j in range(T):
        t2 = dp1[i - 1][j] + dp2[i + 1][T - 1 - j]
        t = max(t, t2)
    ans = max(ans, t + B[i - 1])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappushpop, heappop

N, K = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort()


hq = []
for a, f in zip(A, F):
    heappush(hq, (a * f, f))

c, f = heappop(hq)
while K > 0:
    c += f
    K -= 1
    c, f = heappushpop(hq, (c, f))

print(-c)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse=True)
F.sort()

C = [None] * N
for i, (a, f) in enumerate(zip(A, F)):
    C[i] = (a * f, f)


def solve(x):
    global K, N
    t = 0
    for c, f in C:
        temp = ((c - x) + f - 1) // f
        t += max(0, temp)
        if t > K:
            result = False
            break
    else:
        result = True
    return result


ok = A[0] * F[N - 1]
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations


N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for a, b, c in combinations(L, 3):
    if c < a + b:
        ans += 1

print(ans)


Fixed submission:
from bisect import bisect_left, bisect_right

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += bisect_left(L, L[i] + L[j]) - j - 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
for i in range(M):
    a, b = map(int, input().split())
    C = map(int, input().split())
    A[i] = a
    K[i] = sum([2 ** (i - 1) for i in C])


INF = (1 << 32) - 1
dp = [INF] * (2 ** N)
dp[0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    for j in range(2 ** N):
        dp[j | k] = min(dp[j | k], dp[j] + a)

ans = dp[2 ** N - 1] if dp[2 ** N - 1] < INF else -1
print(ans)


Fixed submission:
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
for i in range(M):
    a, b = map(int, input().split())
    C = map(int, input().split())
    A[i] = a
    K[i] = sum([2 ** (i - 1) for i in C])


INF = (1 << 32) - 1
dp = [[INF] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    for j in range(2 ** N):
        here = dp[i][j]
        dp[i + 1][j] = min(dp[i + 1][j], here)
        dp[i + 1][j | k] = min(dp[i + 1][j | k], dp[i][j | k], here + a)

ans = dp[M][2 ** N - 1] if dp[M][2 ** N - 1] < INF else -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(N):
    for j in range((N + i) // 2, i, -1):
        if S[i:j] in S[j:]:
            ans = max(ans, j - i)
            break

print(ans)


Fixed submission:
def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


N = int(input())
S = input()

ans = 0
for i in range(N):
    A = z_algo(S[i:])
    for idx, ls in enumerate(A):
        if idx - ls >= 0:
            ans = max(ans, ls)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if (j - i) <= (N - j):
            l1 = S[i:j]
            l2 = S[j:]
            if l1 in l2:
                ans = max(ans, len(l1))

print(ans)


Fixed submission:
def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


N = int(input())
S = input()

ans = 0
for i in range(N):
    A = z_algo(S[i:])
    for idx, ls in enumerate(A):
        if idx - ls >= 0:
            ans = max(ans, ls)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()


def lcs(s1, s2):
    I = len(s1)
    J = len(s2)
    dp = [[0] * (J + 1) for _ in range(I + 1)]

    for i in range(I):
        for j in range(J):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    return dp[I][J]


ans = 0
for i in range(1, N):
    s1 = S[0:i]
    s2 = S[i:]
    ans = max(ans, lcs(s1, s2))

print(ans)


Fixed submission:
def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


N = int(input())
S = input()

ans = 0
for i in range(N):
    A = z_algo(S[i:])
    for idx, ls in enumerate(A):
        if idx - ls >= 0:
            ans = max(ans, ls)

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

B = list(map(int, input().split()))
B.append(max(B[0], B[-1]))

ans = 0
for i in range(N):
    ans += min(B[i], B[i - 1])

print(ans)


Fixed submission:
N, K = map(int, input().split())
S = input()
T = []

g = S[0]
cnt = 0
for s in S:
    if s == g:
        cnt += 1
    else:
        T.append(cnt)
        cnt = 1
        g = s
else:
    T.append(cnt)


t = len(T)
for k in range(K):
    t -= 2

if t <= 1:
    print(N - 1)
else:
    print(N - t)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))

divs = []
maxA = sum(A)
for i in range(1, maxA + 1):
    if maxA % i == 0:
        divs.append(i)
        divs.append(maxA // i)

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()


Fixed submission:
from heapq import heappush, heappop


N, K = map(int, input().split())
A = list(map(int, input().split()))

divs = []
maxA = sum(A)
for i in range(1, int(maxA ** 0.5) + 1):
    if maxA % i == 0:
        heappush(divs, -i)
        j = maxA // i
        if i != j:
            heappush(divs, -j)

while True:
    d = -heappop(divs)
    q = []
    asum = 0
    for a in A:
        rest = a % d
        asum += rest
        heappush(q, -rest)
    cnt = 0
    for i in range(asum // d):
        cnt += d - (-heappop(q))
    if cnt <= K:
        print(d)
        exit()

Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil


N, K = map(int, input().split())
A = list(map(int, input().split()))

divs = []
maxA = sum(A)
for i in range(maxA, ceil(maxA ** 0.5) - 1, -1):
    if maxA % i == 0:
        divs.append(i)
        divs.append(maxA // i)

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()


Fixed submission:
from heapq import heappush, heappop


N, K = map(int, input().split())
A = list(map(int, input().split()))

divs = []
maxA = sum(A)
for i in range(1, int(maxA ** 0.5) + 1):
    if maxA % i == 0:
        heappush(divs, -i)
        j = maxA // i
        if i != j:
            heappush(divs, -j)

while True:
    d = -heappop(divs)
    q = []
    asum = 0
    for a in A:
        rest = a % d
        asum += rest
        heappush(q, -rest)
    cnt = 0
    for i in range(asum // d):
        cnt += d - (-heappop(q))
    if cnt <= K:
        print(d)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import islice


N = int(input())
A = list(map(int, input().split()))
B = [0] * N

for i in range(N - 1, 0, -1):
    p = A[i]
    for j in islice(A, i * 2, N, i):
        p ^= j
        B[i] = p ^ A[i]

B[0] = A[0] ^ (sum(B) % 2)


S = []
for i, b in enumerate(B):
    if b == 1:
        S.append(str(i + 1))

if len(S) == 0:
    print(0)
else:
    print(len(S))
    print(' '.join(S))


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

for i in range(N - 1, -1, -1):
    p = A[i]
    j = i + 1
    while i < N:
        if B[i]:
            p ^= 1
        i += j
    B[j - 1] = p

S = [i + 1 for i, c in enumerate(B) if c]

print(len(S))
print(*S)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

N = int(input())
A = [int(input()) for _ in range(N)]
INF = float('inf')

cnt = 0
X = A
while len(X) > 0:
    cnt += 1
    Y = []
    dp = [INF] * (len(X) + 1)
    for a in X:
        idx = bisect_left(dp, a)
        if dp[idx] == INF:
            dp[idx] = a
        else:
            Y.append(a)
    X = Y


print(cnt)


Fixed submission:
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
INF = float('inf')

dp = [-A[0]]
cnt = 1
for i in range(1, N):
    a = -A[i]
    idx = bisect_right(dp, a)
    if idx == cnt:
        dp.append(a)
        cnt += 1
    else:
        dp[idx] = a

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 1
sm = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, M + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = sm[i - 1][j - 1] + 1
        else:
            dp[i][j] = 0
        sm[i][j] = (sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1] + dp[i][j]) % MOD

print(sum([sum(x) % MOD for x in dp]) % MOD)


Fixed submission:
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 1
sm = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, M + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = (sm[i - 1][j - 1] + 1) % MOD
        else:
            dp[i][j] = 0
        sm[i][j] = (sm[i - 1][j] + sm[i][j - 1] - sm[i - 1][j - 1] + dp[i][j]) % MOD

print(sm[N][M] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys


N, M = map(int, input().split())
A = list(map(int, input().split()))

ope = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]

ope.sort(key=lambda x: -x[1])

cnt = 0
for b, c in ope:
    A = A + [c] * b
    cnt += b

    if cnt >= N:
        break

A.sort(reverse=True)

print(sum(A[:N]))


Fixed submission:
import sys


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ope = [list(map(int, x.split())) for x in sys.stdin.readlines()]

ope.sort(key=lambda x: -x[1])

mp = 0
ap = 0
cnt = 0
ans = 0

while cnt < N:
    a = A[ap]
    m = ope[mp][1] if mp < M else 0

    if m >= a:
        mc = min(ope[mp][0], N - cnt)
        ans += m * mc
        cnt += mc
        mp += 1
    else:
        ans += a
        cnt += 1
        ap += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys


N, M = map(int, input().split())
A = list(map(int, input().split()))

ope = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]

ope.sort(key=lambda x: -x[1])

cnt = 0
for b, c in ope:
    A = A + [c] * b
    cnt += b

    if cnt >= N:
        break

A.sort(reverse=True)

print(sum(A[:N]))


Fixed submission:
import sys


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ope = [list(map(int, x.split())) for x in sys.stdin.readlines()]

ope.sort(key=lambda x: -x[1])

mp = 0
ap = 0
cnt = 0
ans = 0

while cnt < N:
    a = A[ap]
    m = ope[mp][1] if mp < M else 0

    if m >= a:
        mc = min(ope[mp][0], N - cnt)
        ans += m * mc
        cnt += mc
        mp += 1
    else:
        ans += a
        cnt += 1
        ap += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

ope = []
for i in range(M):
    ope.append(tuple(map(int, input().split())))

ope.sort(key=lambda x: x[1], reverse=True)

cnt = 0
for b, c in ope:
    A = A + [c] * b
    cnt += b

    if cnt > N:
        break

A.sort(reverse=True)

print(sum(A[:N]))


Fixed submission:
import sys


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ope = [list(map(int, x.split())) for x in sys.stdin.readlines()]

ope.sort(key=lambda x: -x[1])

mp = 0
ap = 0
cnt = 0
ans = 0

while cnt < N:
    a = A[ap]
    m = ope[mp][1] if mp < M else 0

    if m >= a:
        mc = min(ope[mp][0], N - cnt)
        ans += m * mc
        cnt += mc
        mp += 1
    else:
        ans += a
        cnt += 1
        ap += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
def dfs(u):
    for v, w in edge[u]:
        if trail[v] is None:
            trail[v] = (trail[u] + w) % 2
            dfs(v)


N = int(input())
trail = [None] * N
edge = [[] for _ in range(N)]

for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v, w))
    edge[v].append((u, w))

trail[0] = 0
dfs(0)

for t in trail:
    print(t)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(u):
    for v, w in edge[u]:
        if trail[v] is None:
            trail[v] = (trail[u] + w) % 2
            dfs(v)


N = int(input())
trail = [None] * N
edge = [[] for _ in range(N)]

for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v, w))
    edge[v].append((u, w))

trail[0] = 0
dfs(0)

for t in trail:
    print(t)
Buggy python submission (verdict: Runtime Error):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ans = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            if (x + 1) * (y + 1) * (z + 1) <= K:
                ans.append(A[x] + B[y] + C[z])
            else:
                break

ans.sort(revere=True)
print(*ans[:K], sep='\n')


Fixed submission:
from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q = []
x = y = z = 0
heappush(q, (-(A[x] + B[y] + C[z]), (x, y, z)))
done = set((0, 0, 0))
ans = []
for _ in range(K):
    val, (x, y, z) = heappop(q)
    ans.append(-val)
    for i, j, k in [(1, 0, 0), (0, 1, 0), (0, 0, 1)]:
        nx = x + i; ny = y + j; nz = z + k
        if nx < X and ny < Y and nz < Z and (nx, ny, nz) not in done:
            heappush(q, (-(A[nx] + B[ny] + C[nz]), (nx, ny, nz)))
            done.add((nx, ny, nz))

print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
from math import log2

def cntOnes(n, N):
    ret = [0] * N
    i = 0
    while (n >> i) > 0:
        t = 2 ** i
        quot = n // t
        rem = n % t
        if quot % 2 == 1:
            ret[i] = (quot // 2) * t + (rem + 1)
        else:
            ret[i] = (quot // 2) * t
        i += 1
    return ret


A, B = map(int, input().split())

dig = int(log2(B)) + 1
cntA = cntOnes(A - 1, dig)
cntB = cntOnes(B, dig)

ans = 0
for i, (a, b) in enumerate(zip(cntA, cntB)):
    if (a - b) % 2 == 1:
        ans += (1 << i)

print(ans)


Fixed submission:
from math import log2


def cntOnes(n, N):
    ret = [0] * N
    i = 0
    while (n >> i) > 0:
        t = 2 ** i
        quot = n // t
        rem = n % t
        if quot % 2 == 1:
            ret[i] = (quot // 2) * t + (rem + 1)
        else:
            ret[i] = (quot // 2) * t
        i += 1
    return ret


A, B = map(int, input().split())

if B == 0:
    print(0)
    exit()
dig = int(log2(B)) + 1
cntA = cntOnes(A - 1, dig) if A != 0 else [0] * dig
cntB = cntOnes(B, dig)

ans = 0
for i, (a, b) in enumerate(zip(cntA, cntB)):
    if (a - b) % 2 == 1:
        ans += (1 << i)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


def factorization(n):
    arr = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0 and n != 1:
        arr[n] = 1

    return arr


N, M = map(int, input().split())
primes = factorization(M)
primeList = list(primes.elements())

ans = 1
for i in range(2 ** len(primeList)):
    t = 0
    x = 1
    while (i >> t) > 0:
        d = primeList[t] if (i >> t) & 1 else 1
        x *= d
        t += 1
    if M // x >= N:
        ans = max(ans, x)

print(ans)


Fixed submission:
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


def factorization(n):
    arr = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0 and n != 1:
        arr[n] = 1

    return arr


def dfs(i, x):
    global N, M, ans
    if i == len(primeKeys):
        if M // x >= N:
            ans = max(ans, x)
    else:
        for j in range(primes[primeKeys[i]] + 1):
            nx = x * (primeKeys[i] ** j)
            if M // nx >= N:
                dfs(i + 1, nx)
            else:
                break


N, M = map(int, input().split())
primes = factorization(M)
# primeList = list(primes.elements())
primeKeys = list(primes.keys())

ans = 1
dfs(0, 1)

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
cnt = 0
for i in range(1, N + 1):
    k = 0
    for j in range(1, N + 1):
        if i % j == 0:
        k += 1
    if k == 8:
        cnt += 1
print(cnt)

Fixed submission:
N = int(input())
cnt = 0
for i in range(1, N + 1, 2):
    k = 0
    for j in range(1, i + 1):
        if i % j == 0:
            k += 1
    if k == 8:
        cnt += 1
print(cnt)

Buggy python submission (verdict: Runtime Error):
N = int(input())
cnt = 0
for i in range(1, N + 1):
  k = 0
  for j in range(1, N + 1):
   	if i % j == 0:
      k += 1
  if k == 8:
    cnt += 1

print(cnt)
  

Fixed submission:
N = int(input())
cnt = 0
for i in range(1, N + 1, 2):
    k = 0
    for j in range(1, i + 1):
        if i % j == 0:
            k += 1
    if k == 8:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = [0] * 31
if N == 0:
    print(0)
    exit()
else:
    while N != 0:
        i = 1 if N < 0 else 0
        k = pow(-2, i)
        while abs(N) > abs(k):
            i += 2
            k += pow(-2, i)
        ans[i] = 1
        N -= pow(-2, i)

for j in range(30, -1, -1):
    if ans[j] == 1:
        print(''.join(map(str, reversed(ans[:j + 1]))))
        exit()


Fixed submission:
N = int(input())
ans = [0] * 40
if N == 0:
    print(0)
    exit()
else:
    while N != 0:
        i = 1 if N < 0 else 0
        k = pow(-2, i)
        while abs(N) > abs(k):
            i += 2
            k += pow(-2, i)
        ans[i] = 1
        N -= pow(-2, i)

for j in range(39, -1, -1):
    if ans[j] == 1:
        print(''.join(map(str, reversed(ans[:j + 1]))))
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
req = [tuple(map(int, input().split())) for _ in range(M)]
req.sort(key=lambda x: x[1])

res = 0
i = 1
while i <= N:
    remain = [x for x in req if i <= x[0]]
    if len(remain):
        i = remain[0][1]
        res += 1
    else:
        break

print(res)


Fixed submission:
N, M = map(int, input().split())
req = [tuple(map(int, input().split())) for _ in range(M)]
req.sort(key=lambda x: x[1])

res = 0
i = 1
for m in range(M):
    if req[m][0] >= i:
        i = req[m][1]
        res += 1

print(res)