Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02550 (python)

Fixed submission:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Buggy submission (verdict: Runtime Error):
value_index = dict()
 n, x, m = map(int, input().split())
 a = [0] * m
 s = [0] * (m + 1)
 for i in range(m):
     a[i] = x % m
     s[i+1] = s[i] + a[i]
     if i == n - 1:
         print(s[i+1])
         quit()
     if a[i] in value_index:
         break
     value_index[a[i]] = i
     x = x * x % m 
 l = value_index[a[i]]
 r = i 
 loop_sum = s[r] - s[l]
 loop_n = (n - l) // (r - l)
 rem = (n - l) % (r - l) 
 ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
 print(ans)

Buggy submission (verdict: Runtime Error):

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Buggy submission (verdict: Runtime Error):

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * m
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)
ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)
Problem p02779 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
d = set()
for x in a:
  if x in d:
    print("NO")
    quit()
  d.add(x)
print("YES")

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input.split()))
d = set()
for x in a:
  if x in d:
    print("NO")
    quit()
  d.add(x)
print("YES")
Problem p02862 (python)

Fixed submission:
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 10 ** 9 + 7
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    quit()
n = (x + y) // 3
if x < n or y < n:
    print(0)
    quit()

m = min(x, y) - n
fac, inv = factorial(n, mod)
print(fac[n] * inv[n-m] * inv[m] % mod) # nCm

Buggy submission (verdict: Runtime Error):
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

mod = 10 ** 9 + 7
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    quit()
n = (x + y) // 3
m = min(x, y) - n

fac, inv = factorial(n, mod)
print(fac[n] * inv[n-m] * inv[m] % mod) # nCm
Problem p02880 (python)

Fixed submission:
n = int(input())
i = 1
while i * i <= n:
    if n % i == 0:
        j = n // i
        if i < 10 and j < 10:
            print("Yes")
            quit()
    i += 1
print("No")

Buggy submission (verdict: Runtime Error):
n = int(input())
i = 1
while i * i <= n:
  if n % i != 0:
    continue
  j = n // i
  if i < 10 and j < 10:
    print("Yes")
	quit()
print("No")
Problem p03016 (python)

Fixed submission:

def mul_square_matrix(a, b, mod):
    n = len(a)
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % mod
    return ret


def power_square_matrix(mat:list, k, mod):
    n = len(mat)
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        ret[i][i] = 1
    while k > 0:
        if k % 2 == 1:
            ret = mul_square_matrix(ret, mat, mod)
        mat = mul_square_matrix(mat, mat, mod)
        k //= 2
    return ret

l, a, b, m = map(int, input().split())
s_foot = a + b * (l - 1)
digit_n = len(str(s_foot))
count_digit_n = [0] * (digit_n + 1)
d = 1
for i in range(1, digit_n + 1):
    d *= 10
    x = min(d - 1, s_foot) - a
    if x < 0:
        continue
    n = x // b
    count_digit_n[i] = n + 1

for i in range(digit_n, 0, -1):
    count_digit_n[i]  -= count_digit_n[i - 1]

d = 1
x = [[0], [a], [1]]
for n in count_digit_n[1:]:
    d = d * 10 % m
    if n == 0:
        continue
    mat = [[d, 1, 0], [0, 1, b], [0, 0, 1]]
    mat = power_square_matrix(mat, n, m)
    for i in range(3):
        x[i][0] = sum([mat[i][j] * x[j][0] for j in range(3)]) % m
print(x[0][0])

Buggy submission (verdict: Runtime Error):
import numpy

def power(mat:numpy.matrix, n, mod):
    ret = mat
    n -= 1
    while n > 0:
        if n % 2 == 1:
            ret = ret @ mat % mod
        mat = mat @ mat % mod
        n //= 2
    return ret

l, a, b, m = map(int, input().split())
s_foot = a + b * (l - 1)
digit_n = len(str(s_foot))
count_digit_n = [0] * (digit_n + 1)
d = 10
for i in range(1, digit_n + 1):
    x = min(d - 1, s_foot) - a
    if x < 0:
        continue
    n = x // b
    count_digit_n[i] = n + 1
    d *= 10

for i in range(digit_n, 0, -1):
    count_digit_n[i]  -= count_digit_n[i - 1]

d = 10
i = 0
x = numpy.matrix([[0], [a], [1]])

for n in count_digit_n:
    if n == 0:
        continue
    mat = numpy.matrix([[d, 1, 0], [0, 1, b], [0, 0, 1]])
    x = power(mat, n, m) @ x % m
    d = d * 10 % m
print(x[0][0][0])
Problem p03253 (python)

Fixed submission:
def factorize(n):
    factor = []
    if n % 2 == 0:
        f = [2, 1]
        n //= 2
        while n % 2 == 0:
            n //= 2
            f[1] += 1
        factor.append(f)
    k = 3
    while k * k <= n:
        if n % k == 0:
            f = [k, 1]
            n //= k
            while n % k == 0:
                n //= k
                f[1] += 1
            factor.append(f)
        k += 2
    if n != 1:
        factor.append([n, 1])
    return factor

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

n, m = map(int, input().split())
if m == 1:
    print(1)
    quit()
mod = 10 ** 9 + 7
f = factorize(m)
max_k = max(i for _, i in f)
fac, inv = factorial(n + max_k - 1, mod)
ans = 1
for _, k in f:
    ans = ans * fac[n + k - 1] % mod * inv[n - 1] % mod * inv[k] % mod
print(ans)

Buggy submission (verdict: Runtime Error):
def factorize(n):
    factor = []
    if n % 2 == 0:
        f = [2, 1]
        n //= 2
        while n % 2 == 0:
            n //= 2
            f[1] += 1
        factor.append(f)
    k = 3
    while k * k <= n:
        if n % k == 0:
            f = [k, 1]
            n //= k
            while n % k == 0:
                n //= k
                f[1] += 1
            factor.append(f)
        k += 2
    if n != 1:
        factor.append([n, 1])
    return factor

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

n, m = map(int, input().split())
mod = 10 ** 9 + 7
f = factorize(m)
max_k = max(i for _, i in f)
fac, inv = factorial(n + max_k - 1, mod)

ans = 1
for _, k in f:
    ans = ans * fac[n + k - 1] % mod * inv[n - 1] % mod * inv[k] % mod
print(ans)
Problem p02572 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
T = sum(A)
ans = 0
for i in range(N):
  T -= A[i]
  ans += A[i] * T
  ans %= 10 ** 9 + 7
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
N = int(input())
A = list(map(int, input().split()))
print(np.sum(np.tril(np.outer(np.array(A), np.array(A)), k = -1)) % (10 ** 9 + 7))
Problem p02754 (python)

Fixed submission:
N, A, B = map(int, input().split())
if A == 0:
  print(0)
elif A > N or B == 0:
  print(N)
else:
  M = N // (A + B)
  if N - M * (A + B) > A:
    print(A * M + A)
  else:
    print(N - M * B)

Buggy submission (verdict: Runtime Error):
N, A, B = map(int, input().split())
if A == :
  print(0)
else:
  print(N) if A > N else print(A if N < (A + B) else N - B)
Problem p02833 (python)

Fixed submission:
L = [10, 50, 250, 1250, 6250, 31250, 156250, 781250, 3906250, 19531250, 97656250, \
     488281250, 2441406250, 12207031250, 61035156250, 305175781250, 1525878906250, \
     7629394531250, 38146972656250, 190734863281250, 953674316406250, \
     4768371582031250, 23841857910156250, 119209289550781250, 596046447753906250]
N = int(input())
A = 0
if N % 2 == 0:
  for i in L:
    A += N // i
print(A)

Buggy submission (verdict: Runtime Error):
N = int(input())
if N % 2 == 0:
else:
  print(0)
Problem p02695 (python)

Fixed submission:
from itertools import combinations_with_replacement

N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

print(max(sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c) for A in combinations_with_replacement(range(1, M + 1), N)))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max((solve(A + [i]) for i in range(A[-1], M + 1)), default=0)

print(solve([1]))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max((solve(A + [i]) for i in range(A[-1], M + 1)))

print(solve([1]))

Buggy submission (verdict: Runtime Error):
N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max((solve(A + [i]) for i in range(A[-1], M + 1)), default=0)

print(solve([1]))

Buggy submission (verdict: Runtime Error):
N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max(solve(A + [i]) for i in range(A[-1], M + 1))

print(solve([1]))
Problem p02763 (python)

Fixed submission:
# https://atcoder.jp/contests/abc157/tasks/abc157_e

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)

N, S, Q = ni(), list(ns()), ni()

B = [BIT(N) for _ in range(26)]
for i, s in enumerate(S, 1):
    B[ord(s) - ord('a')].add(i, 1)

A = []
for _ in range(Q):
    if ni() == 1:
        i, c = ni(), ns()
        B[ord(S[i - 1]) - ord('a')].add(i, -1)
        S[i - 1] = c
        B[ord(c) - ord('a')].add(i, 1)
    else:
        l, r = ni(), ni()
        A.append(sum(b.sum(l - 1) < b.sum(r) for b in B))

print("\n".join(map(str, A)))

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc157/tasks/abc157_e

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

sc = iter(open(0).read().split())
ni = lambda: int(next(sc))
ns = lambda: next(sc)
nc = lambda: ord(next(sc)) - ord('a')

N, S, Q = ni(), list(ns()), ni()

B = [BIT(N) for _ in range(26)]
for i, s in enumerate(S, 1):
    B[ord(s) - ord('a')].add(i, 1)

A = []
for _ in range(Q):
    if ni() == 1:
        i, c = ni(), nc()
        B[ord(S[i - 1]) - ord('a')].add(i, -1)
        S[i - 1] = c
        B[c].add(i, 1)
    else:
        l, r = ni(), ni()
        A.append(sum(b.sum(l - 1) < b.sum(r) for b in B))

print("\n".join(map(str, A)))
Problem p02769 (python)

Fixed submission:
mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

mc = ModComb(2 * N)

ans = mc.nCk(2 * N - 1, N - 1)
if K + 1 < N:
    ans += sum((mod - mc.nCk(N, i)) * mc.nCk(N - 1, i) % mod for i in range(K + 1, N)) % mod

print(ans % mod)

Buggy submission (verdict: Runtime Error):
Point = complex


N, *XY = map(int, open(0).read().split())

P = [Point(x, y) for x, y in zip(*[iter(XY)] * 2)]

def max_distance(center):
    return max(abs(center - p) for p in P)

def ternary_search(f, left, right, MAX_ITER=100):
    for _ in range(MAX_ITER):
        m1 = (left * 2 + right) / 3
        m2 = (left + right * 2) / 3
        if f(m1) < f(m2):
            right = m2
        else:
            left = m1
    return f(left)

def g(x):
    return ternary_search(lambda y: max_distance(Point(x, y)), -1000, 1000)

print(ternary_search(g, -1000, 1000))
Problem p02781 (python)

Fixed submission:
def nCk(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if N == 0 and K > 0:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    if M > K:
        res += nCk(M - 1, K) * (9 ** K)

    return res


N = int(input())
K = int(input())

print(solve(N, K))

Buggy submission (verdict: Runtime Error):
def nCk(n, k):
    if n < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if K == 0:
        return 1

    M = len(N)
    res = solve(N[1:], K - 1)
    res += (int(N[0]) - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))
    res += nCk(M - 1, K) * (9 ** K)

    return res


N = input()
K = int(input())

print(solve(N, K))

Buggy submission (verdict: Runtime Error):
N = input()
K = int(input())


M = len(N)

if K == 1:
    ans = (M - 1) * 9 + int(N[0])
    print(ans)

if K == 2:
    ans = int(N[1])
    ans += (M - 2) * 9
    ans += (int(N[0]) - 1) * (M - 1) * 9
    ans += (M - 1) * (M - 2) // 2 * 9 * 9
    print(ans)

if K == 3:
    ans = int(N[2])
    ans += (M - 3) * 9
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (M - 2) * (M - 3) // 2 * 9 * 9
    ans += (int(N[0]) - 1) * (M - 1) * (M - 2) // 2 * 9 * 9
    ans += (M - 1) * (M - 2) * (M - 3) // 6 * 9 * 9 * 9
    print(ans)

Buggy submission (verdict: Runtime Error):
N = input()
K = int(input())


M = len(N)

if K == 1:
    ans = (M - 1) * 9 + int(N[0])
    print(ans)

if K == 2:
    ans = int(N[1])
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (int(N[0]) - 1) * (M - 1) * 9
    ans += (M - 1) * (M - 2) // 2 * 9 * 9
    print(ans)

if K == 3:
    ans = int(N[2])
    ans += (M - 3) * 9
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (M - 2) * (M - 3) // 2 * 9 * 9
    ans += (int(N[0]) - 1) * (M - 1) * (M - 2) // 2 * 9 * 9
    ans += (M - 1) * (M - 2) * (M - 3) // 6 * 9 * 9 * 9
    print(ans)
Problem p02793 (python)

Fixed submission:
from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()

Buggy submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce

lcm = lambda a, b: b // lcm(a, b) * a
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = reduce(lcm, A) % mod
print(sum(L * pow(a, mod - 2, mod) % mod for a in A) % mod)
Problem p02862 (python)

Fixed submission:
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

mod = 10 ** 9 + 7
mc = ModComb(3 * 10 ** 6, mod)

X, Y = map(int, input().split())
if (2 * X - Y) % 3 != 0 or (X - 2 * Y) % 3 != 0:
    print(0)
    quit()

b = (2 * X - Y) // 3
a = (-X + 2 * Y) // 3

print(mc.nCk(a + b, a))

Buggy submission (verdict: Runtime Error):
from functools import reduce

def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    mod_mul = lambda a, b: a * b % mod
    numer = reduce(mod_mul, range(n - k + 1, n + 1))
    denom = reduce(mod_mul, range(1, k + 1))
    return numer * pow(denom, mod - 2, mod) % mod

X, Y = map(int, input().split())

b = (2 * X - Y) // 3
a = (-X + 2 * Y) // 3

if (X + Y) % 3 != 0 or a < 0 or b < 0:
    print(0)
else:
    print(nCk(a + b, a))
Problem p02863 (python)

Fixed submission:
N, T, *AB = map(int, open(0).read().split())

dp = [0] * (T + max(AB[::2]))
for w, v in sorted(zip(*[iter(AB)] * 2)):
    for i in reversed(range(T)):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

Buggy submission (verdict: Runtime Error):
from numpy import*
(N,T),*L=loadtxt(open(0)).tolist()
d=zeros(1e4,int)
for w,v in sorted(L):t=d[w:T+w];s=d[:T]+v;t[t<s]=s
print(max(d))
Problem p02998 (python)

Fixed submission:
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

    def same(self, x, y):
        return (self.find(x) == self.find(y))

    def size(self, x):
        return -self.data[self.find(x)]


MAX = 10 ** 5 + 10
uf = UnionFind(2 * MAX)

N, *XY = map(int, open(0).read().split())

for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y + MAX)

X = Counter(uf.find(i) for i in range(MAX))
Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
res = sum(X[i] * Y[i] for i in range(MAX * 2))

print(res - N)

Buggy submission (verdict: Runtime Error):
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

    def same(self, x, y):
        return (self.find(x) == self.find(y))

    def size(self, x):
        return -self.data[self.find(x)]


MAX = 10 ** 5
uf = UnionFind(2 * MAX)

N, *XY = map(int, open(0).read().split())

for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y + MAX)

X = Counter(uf.find(i) for i in range(MAX))
Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
res = sum(X[i] * Y[i] for i in range(MAX * 2))

print(res - N)
Problem p03013 (python)

Fixed submission:
mod = 1000000007

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]

for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()

fib = [-1] * (N + 1)
fib[0] = 1
fib[1] = 1
for i in range(2, len(fib)):
    fib[i] = fib[i - 1] + fib[i - 2]


ans = 1
pre = -1
lo = 0
for a in A:
    f = fib[a - 1 - lo]
    ans = (ans * f) % mod

    lo = a + 1
    pre = a

print(ans)

Buggy submission (verdict: Runtime Error):
mod = 1000000007
 
N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]
 
for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()
 
memo = {0: 1, 1: 1, 2: 2, 3: 3}
 
def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
 
ans = 1
pre = -1
lo = 0
for a in A:
    f = fib(a - 1 - lo)
    ans = (ans * f) % mod
 
    lo = a + 1
    pre = a
 
print(ans)

Buggy submission (verdict: Runtime Error):
mod = 1000000007

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]

for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()

memo = {0: 1, 1: 1, 2: 2, 3: 3}

def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

ans = 1
pre = -1
lo = 0
for a in A:
    f = fib(a - 1 - lo)
    ans = (ans * f) % mod

    lo = a + 1
    pre = a

print(ans)