Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
N, M = map(int, input().split())
link = {i: [] for i in range(1, N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    link[u].append(v)
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {i: False for i in range(1, N+1)}
dist = {i: INF for i in range(1, N+1)}  # distance
# prev = {i: -1 for i in range(1, N+1)}  # for extract min cost path
pq = []
# initialize
dist[S] = 0
heappush(pq, (0, S))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        # if vstd[v]:
        #     continue
        for w in link[v]:
            # if vstd[w]:
            #     continue
            for x in link[w]:
                if vstd[x]:
                    continue
                if dist[u] + 1 < dist[x]:
                    dist[x] = dist[u] + 1
                    # prev[v] = u
                    heappush(pq, (dist[x], x))

print(dist[T] if dist[T] != INF else -1)


Fixed submission:
from heapq import heappop, heappush
N, M = map(int, input().split())
link = {(i, j) : [] for i in range(1, N+1) for j in range(3)}
for _ in range(M):
    u, v = map(int, input().split())
    link[(u, 0)].append((v, 1))
    link[(u, 1)].append((v, 2))
    link[(u, 2)].append((v, 0))
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {(i, j): False for i in range(1, N+1) for j in range(3)}
dist = {(i, j): INF for i in range(1, N+1) for j in range(3)}  # distance
# prev = {i: -1 for i in range(1, N+1)}  # for extract min cost path
pq = []
# initialize
dist[(S, 0)] = 0
heappush(pq, (0, (S, 0)))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        if vstd[v]:
            continue
        if dist[u] + 1 < dist[v]:
            dist[v] = dist[u] + 1
            # prev[v] = u
            heappush(pq, (dist[v], v))


print(dist[(T, 0)] // 3 if dist[(T, 0)] % 3 == 0 else -1)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

# guchoku case

# dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

# for i in range(N+1):
#     dp[1][i] = 1
# for i in range(K):
#     for j in range(1,N+1):
#         for k in range(1, N // j + 1):
#             dp[i+1][j] += dp[i][k]
#             dp[i+1][j] %= MOD

JN = [0]  # N//j table
j = 1
while j*j<N:
    if j not in JN:
        JN.append(j)
    if N//j not in JN:
        JN.append(N//j)
    j += 1

JN.sort()
PJN = {JN[i]: JN[i-1] for i in range(1, len(JN))}  # prev jn

dp = [{0: 0} for _ in range(K)]
cdp = [{0: 0} for _ in range(K)]
w = dict()

# init dp
prv = 0
for i, jn in enumerate(JN):
    dp[0][jn] = 1
    w[jn] = jn - prv
    cdp[0][jn] = jn
    prv = JN[i]

for i in range(K-1):
    for jn in JN[1:]:
        dp[i+1][jn] = cdp[i][N//jn]
        dp[i+1][jn] %= MOD
        cdp[i+1][jn] = cdp[i+1][PJN[jn]] + dp[i+1][jn] * w[jn]
        cdp[i+1][jn] %= MOD

print(cdp[-1][N])


Fixed submission:
from collections import deque
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

# guchoku case

# dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

# for i in range(N+1):
#     dp[1][i] = 1
# for i in range(K):
#     for j in range(1,N+1):
#         for k in range(1, N // j + 1):
#             dp[i+1][j] += dp[i][k]
#             dp[i+1][j] %= MOD

JN = deque()  # N//j table
SQN = int(N**0.5)
JN.append(SQN)

if SQN**2 != N:
    JN.append(N//SQN)
for j in range(SQN-1, 0, -1):
    JN.appendleft(j)
    JN.append(N//j)
JN.appendleft(0)

# JN.sort()
# PJN = {JN[i]: JN[i-1] for i in range(1, len(JN))}  # prev jn
LJN = len(JN)

dp = [[0 for _ in range(LJN)] for _ in range(K)]
cdp = [[0 for _ in range(LJN)] for _ in range(K)]
w = [0 for _ in range(LJN)]

# init dp
prv = 0
for i in range(1,LJN):
    jn = JN[i]
    dp[0][i] = 1
    w[i] = jn - prv
    cdp[0][i] = jn
    prv = JN[i]

for i in range(K-1):
    for j in range(1,LJN):
        dp[i+1][j] = cdp[i][LJN-j]
        dp[i+1][j] %= MOD
        cdp[i+1][j] = cdp[i+1][j-1] + dp[i+1][j] * w[j]
        cdp[i+1][j] %= MOD

print(cdp[-1][-1])
Buggy python submission (verdict: Runtime Error):
from itertools import combinations

N = int(input())
P = []
for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

memo = dict()
for (a, b) in combinations(P, 2):
    p, q = a[0] - b[0], a[1] - b[1]
    if p < 0:
        p, q = -p, -q
    elif p == 0 and q < 0:
        q = -q
    if (p, q) in memo:
        memo[(p, q)] += 1
    else:
        memo[(p, q)] = 1

print(N - max(memo.values()))


Fixed submission:
from itertools import combinations

N = int(input())
P = []
for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

memo = dict()
for (a, b) in combinations(P, 2):
    p, q = a[0] - b[0], a[1] - b[1]
    if p < 0:
        p, q = -p, -q
    elif p == 0 and q < 0:
        q = -q
    if (p, q) in memo:
        memo[(p, q)] += 1
    else:
        memo[(p, q)] = 1

print(N - max(memo.values()) if N > 1 else 1)
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
NMAX = 10 ** 5

A = []
for _ in range(M):
    A.append(int(input()))

dp = [None for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if A[0] == 1 else 1
for i in range(2, N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[-1])


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

NG = [False for _ in range(N+1)]
for _ in range(M):
    NG[int(input())] = True

dp = [None for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if NG[1] else 1
for i in range(2, N+1):
    if NG[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import sys
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
NMAX = 10 ** 5
sys.setrecursionlimit(10 ** 6)

memo = [None for _ in range(NMAX+1)]
def fibo(n):
    if memo[n]:
        return memo[n]
    if n == 0:
        return 0
    elif n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

nc = 1
b = 0
for i in range(M):
    a = int(input())
    nc = (nc * fibo(a - b)) % MOD
    b = a + 1

nc = (nc * fibo(N + 1 - b)) % MOD

print(nc)


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

NG = [False for _ in range(N+1)]
for _ in range(M):
    NG[int(input())] = True

dp = [None for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if NG[1] else 1
for i in range(2, N+1):
    if NG[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import sys
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
NMAX = 10 ** 5
sys.setrecursionlimit(NMAX+1)

memo = [None for _ in range(NMAX+1)]
def fibo(n):
    if memo[n]:
        return memo[n]
    if n == 0:
        return 0
    elif n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

nc = 1
b = 0
for i in range(M):
    a = int(input())
    nc = (nc * fibo(a - b)) % MOD
    b = a + 1

nc = (nc * fibo(N + 1 - b)) % MOD

print(nc)


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

NG = [False for _ in range(N+1)]
for _ in range(M):
    NG[int(input())] = True

dp = [None for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if NG[1] else 1
for i in range(2, N+1):
    if NG[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))
CB = []
for _ in range(M):
    b, c = map(int, input().split())
    CB.append((c, b))

# ascend
A.sort()

# descend
CB.sort(reverse=True)

# fill convert ary
conv = []
for cb in CB:
    c, b = cb
    conv.extend([c] * b)

cl = len(conv)

sum = 0
for i in range(N):
    if i >= cl:
        sum += A[i]
    else:
        sum += max(A[i], conv[i])

print(sum)


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
CB = []
for _ in range(M):
    b, c = map(int, input().split())
    CB.append((c, b))

# ascend
A.sort()

# descend
CB.sort(reverse=True)

# fill convert ary
conv = []
for cb in CB:
    c, b = cb
    conv.extend([c] * b)
    if len(conv) >= N:
        break

cl = len(conv)

sum = 0
for i in range(N):
    if i >= cl:
        sum += A[i]
    else:
        sum += max(A[i], conv[i])

print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

import heapq


a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

index_hstr = []
deliciouses = []
# priority queue
pq = []
heapq.heappush(pq, (-a[0] - b[0] - c[0], 0, 0, 0))
index_hstr.append((0, 0, 0))

for t in range(k):
    deli, i, j, k = heapq.heappop(pq)
    if i+1<x and (i+1, j, k) not in index_hstr:
        heapq.heappush(pq, (-a[i+1] - b[j] - c[k], i+1, j, k))
        index_hstr.append((i+1, j, k))
    if j+1<y and (i, j+1, k) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j+1] - c[k], i, j+1, k))
        index_hstr.append((i, j+1, k))
    if k+1<z and (i, j, k+1) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j] - c[k+1], i, j, k+1))
        index_hstr.append((i, j, k+1))
    deliciouses.append(-deli)


print('\n'.join(str(i) for i in deliciouses))


Fixed submission:
# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
ab.extend([i+j for j in b for i in a])
ab.sort(reverse=True)

abc = []
abc.extend([i+j for j in ab[:k] for i in c])
abc.sort(reverse=True)

print('\n'.join(str(i) for i in abc[:k]))

Buggy python submission (verdict: Runtime Error):
# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

import heapq


a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

index_hstr = []
deliciouses = []
# priority queue
pq = []
heapq.heappush(pq, (-a[0] - b[0] - c[0], 0, 0, 0))
index_hstr.append((0, 0, 0))

for t in range(k):
    deli, i, j, k = heapq.heappop(pq)
    if (i+1, j, k) not in index_hstr:
        heapq.heappush(pq, (-a[i+1] - b[j] - c[k], i+1, j, k))
        index_hstr.append((i+1, j, k))
    if (i, j+1, k) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j+1] - c[k], i, j+1, k))
        index_hstr.append((i, j+1, k))
    if (i, j, k+1) not in index_hstr:
        heapq.heappush(pq, (-a[i] - b[j] - c[k+1], i, j, k+1))
        index_hstr.append((i, j, k+1))
    deliciouses.append(-deli)


pass


Fixed submission:
# input
x, y, z, k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
ab.extend([i+j for j in b for i in a])
ab.sort(reverse=True)

abc = []
abc.extend([i+j for j in ab[:k] for i in c])
abc.sort(reverse=True)

print('\n'.join(str(i) for i in abc[:k]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import combinations
N = int(input())
S = input()
MOD = 10**9 + 7

C = Counter(S)
ans = 0
for i in range(1, min(N+1, 27)):
    for prod in combinations(C.values(), i):
        a = 1
        for p in prod:
            a *= p
            a %= MOD
        ans += a
        ans %= MOD

print(ans)     


Fixed submission:
# input
n = int(input())
s = input()


prod = 1
for char in set(s):
    num = s.count(char)
    prod *= (num + 1)

print((prod - 1) % (pow(10, 9) + 7))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import combinations
N = int(input())
S = input()
MOD = 10**9 + 7

C = Counter(S)
ans = 0
for i in range(1, N+1):
    for prod in combinations(C.values(), i):
        a = 1
        for p in prod:
            a *= p
            a %= MOD
        ans += a
        ans %= MOD

print(ans)     


Fixed submission:
# input
n = int(input())
s = input()


prod = 1
for char in set(s):
    num = s.count(char)
    prod *= (num + 1)

print((prod - 1) % (pow(10, 9) + 7))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import combinations
N = int(input())
S = input()
MOD = 10**9 + 7

C = Counter(S)
ans = 0
for i in range(1, N+1):
    for prod in combinations(C.values(), i):
        a = 1
        for p in prod:
            a *= p
            a %= MOD
        ans += a
        ans %= MOD

print(ans)     


Fixed submission:
# input
n = int(input())
s = input()


prod = 1
for char in set(s):
    num = s.count(char)
    prod *= (num + 1)

print((prod - 1) % (pow(10, 9) + 7))
Buggy python submission (verdict: Time Limit Exceeded):
# input
n = int(input())

c = []
dp = [0] * (n + 1)
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in c and c[-1] is not stone:
            plc = len(c) - 1 - c[::-1].index(stone)
            dp[i + 1] = dp[i] + dp[plc + 1]
        else:
            dp[i + 1] = dp[i]
    c.append(stone)

print(dp[-1])


Fixed submission:
# input
n = int(input())

mod = pow(10, 9) + 7
c = []
dp = [0] * (n + 1)
stone_history = dict()
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in stone_history and c[-1] != stone:
            dp[i + 1] = dp[i] + stone_history[stone]
        else:
            dp[i + 1] = dp[i]

    stone_history[stone] = dp[i + 1]
    c.append(stone)

print(dp[-1] % mod)
Buggy python submission (verdict: Time Limit Exceeded):
# input
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [None for _ in range(N)]
# initiate
dp[0] = 0

for i in range(1, N):
    min_ = min(dp[k] + abs(H[k]-H[i]) for k in range(max(0, i-K), i))
    dp[i] = min_

print(dp[-1])
pass

Fixed submission:
# input
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [None for _ in range(N)]
# initiate
dp[0] = 0

for i in range(1, N):
    min_ = min(dp[k] + abs(H[k]-H[i]) for k in range(max(0, i-K), i))
    dp[i] = min_

print(dp[-1])
pass
Buggy python submission (verdict: Time Limit Exceeded):
# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    dp[i] = [max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1]) if W[i-1] <= w else dp[i-1][w] for w in range(M+1)]
    # for w in range(M+1):
    #     if W[i-1] <= w:
    #         dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
    #     else:
    #         dp[i][w] = dp[i-1][w]


print(max(dp[-1]))


Fixed submission:
# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    for w in range(M+1):
        if W[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
        else:
            dp[i][w] = dp[i-1][w]


print(max(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    for w in range(M+1):
        if W[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
        else:
            dp[i][w] = dp[i-1][w]


print(max(dp[-1]))


Fixed submission:
# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(M+1)] for _ in range(N+1)]
dp[0] = [0 for _ in range(M+1)]
for i in range(1, N+1):
    for w in range(M+1):
        if W[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i-1]] + V[i-1])
        else:
            dp[i][w] = dp[i-1][w]


print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(N*max(V)+1)] for _ in range(N+1)]
dp[0] = [10**9 for _ in range(N*max(V)+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(N*max(V)+1):
        if V[i-1] >= v:
            dp[i][v] = min(dp[i-1][v], W[i-1])
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i-1]] + W[i-1])


print(max(i for i, w in enumerate(dp[-1]) if w <= M))


Fixed submission:
# input
N, M = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[None for __ in range(N*max(V)+1)] for _ in range(N+1)]
dp[0] = [10**9 for _ in range(N*max(V)+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(N*max(V)+1):
        if V[i-1] >= v:
            dp[i][v] = min(dp[i-1][v], W[i-1])
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i-1]] + W[i-1])


print(max(i for i, w in enumerate(dp[-1]) if w <= M))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    V[x].append(y)

dp = [None for _ in range(N)]

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))


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

N, M = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    V[x].append(y)

dp = [None for _ in range(N)]

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    V[x].append(y)

dp = [None for _ in range(N)]

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))


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

N, M = map(int, input().split())
V = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    V[x].append(y)

dp = [None for _ in range(N)]

def dfs(x):
    if dp[x] is not None:
        return dp[x]
    if not V[x]:
        dp[x] = 0
        return 0
    l = max(dfs(v) for v in V[x]) + 1
    dp[x] = l
    return l

print(max(dfs(v) for v in range(N)))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = [0]
P.extend(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 1

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i-1][j-1] * P[i] + dp[i-1][j] * (1-P[i])

print(dp[-1][N//2+1])


Fixed submission:
N = int(input())
P = [0]
P.extend(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 1

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = dp[i-1][j-1] * P[i] + dp[i-1][j] * (1-P[i])

print(dp[-1][N//2+1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

max_dist = 0
judge = []
for (x, y) in P:
    dist = abs(x) + abs(y)
    max_dist = max(max_dist, dist)
    judge.append(dist % 2 == 0)

if all(judge) or not any(judge):
    print(max_dist)
    print(*([1] * max_dist))
    for (x, y) in P:
        com = ''
        com += abs(x) * ('R' if x > 0 else 'L')
        com += abs(y) * ('U' if y > 0 else 'D')
        com += 'LR' * ((max_dist - abs(x) - abs(y)) // 2)
        print(com)
else:
    print(-1)


Fixed submission:
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

odd = []
for (x, y) in P:
    dist = abs(x) + abs(y)
    odd.append(dist % 2 != 0)

valid = True
even = False
if all(odd):
    pass
elif not any(odd):
    even = True
else:
    valid =False

if valid:

    M = 31
    if even:
        print(M+1)
        print(*([1 << m for m in range(M)] + [1]))
    else:
        print(M)
        print(*[1 << m for m in range(M)])

    for (x, y) in P:
        u = x + y
        v = x - y
        if even:
            u += 1
            v += 1
        if u >= 0 and v >= 0:
            A = 'R'
            B = 'U'
            C = 'D'
            D = 'L'
        elif u >= 0 and v < 0:
            v *= -1
            A = 'U'
            B = 'R'
            C = 'L'
            D = 'D'
        elif u < 0 and v >= 0:
            u *= -1
            A = 'D'
            B = 'L'
            C = 'R'
            D = 'U'
        elif u < 0 and v < 0:
            u *= -1
            v *= -1
            A = 'L'
            B = 'D'
            C = 'U'
            D = 'R'

        ans = ''
        wa = ((1 << M) - 1 - u) // 2
        sa = ((1 << M) - 1 - v) // 2
        for i in range(M):
            check = str(wa >> i & 1) + str(sa >> i & 1)
            if check == '00':
                ans += A
            elif check == '01':
                ans += B
            elif check == '10':
                ans += C
            elif check == '11':
                ans += D
        if even:
            ans += 'L'
        print(ans)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cnt = 0
    for l, r in combinations(range(N+1),2):
        if C[l]<=C[r]:
            cnt += 1
    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)


Fixed submission:
from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cmin = min(C)
    for i in range(N+1):
        C[i] -= cmin  # offset
    cmax = max(C)+1
    fw = FenwickTree(cmax)
    cnt = 0
    for i in range(N+1):
        cnt += fw.sum(C[i])
        fw.add(C[i], 1)

    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)